转载

二叉搜索树与双向链表

二叉搜索树与双向链表

题目:

输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。

思想:

递归思想

代码:

public class Solution {
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null) return null;
        if(pRootOfTree.left != null) {
            TreeNode temp = Convert(pRootOfTree.left);
            while(temp.right != null) temp = temp.right;
            pRootOfTree.left = temp;
            temp.right = pRootOfTree;
        }

        if(pRootOfTree.right != null) {
            TreeNode temp = Convert(pRootOfTree.right);
            pRootOfTree.right = temp;
            temp.left = pRootOfTree;
        }

        TreeNode temp = pRootOfTree;
        while(temp.left != null)  temp = temp.left;
        return temp;
    }
}
正文到此结束
本文目录