博客

题目链接:

二叉搜索树与双向链表

思路1：

搜索二叉树转换成有序双向链表 = 左子树构建得双向有序链表+根节点+右子树构建得双向有序链表

用图分析：

代码：

public class Solution {
    public TreeNode CreateList(TreeNode pCur){
        if(pCur==null){
            return null;
        }
        TreeNode leftTree = CreateList(pCur.left);//将左子树创建为双向链表
        TreeNode rightTree = CreateList(pCur.right);//将左子树创建为双向链表
        
        if(leftTree!=null){
            while(leftTree.right!=null){//遍历找到左子树的最右边结点
                leftTree=leftTree.right;
            }
            leftTree.right=pCur;
            pCur.left=leftTree;
        }
        if(rightTree!=null){
            while(rightTree.left!=null){//遍历找到右子树最左边的结点
                rightTree=rightTree.left;
            }
            pCur.right=rightTree;
            rightTree.left=pCur;
        }
        return pCur;
    }
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree==null){
            return null;
        }
        CreateList(pRootOfTree);
        TreeNode head=pRootOfTree;
        while(head.left!=null){
            head=head.left;
        }
        return head;
    }
}

在这里可以看到，并没有刻意去控制链表的头和尾的null，那是因为一棵用二叉搜索树创建的链表的头

节点的left

和

尾节点的right

自然而然是

null

。

思路2：

引入一个变量prev，用来记录pCur的前一个结点。

遍历的过程是中序遍历：pCur的顺序是中序遍历的顺序，prev的顺序也是中序遍历得顺序。

public class Solution {
    TreeNode prev=null;//prev指向pCur的前一个结点
    public void CreateList(TreeNode pCur){
        if(pCur==null){
            return;
        }
        CreateList(pCur.left);
        pCur.left=prev;
        if(prev!=null){
            prev.right=pCur;
        }
        prev=pCur;//让prev指向当前结点
        CreateList(pCur.right);
    }
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree==null){
            return null;
        }
        CreateList(pRootOfTree);
        TreeNode head=pRootOfTree;
        while(head.left!=null){
            head=head.left;
        }
        return head;
    }
}