题意整理

  • 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。

方法一（递归）

1.解题思路

由于二叉搜索树的中序遍历是从小到大依次输出的，所以可以利用中序遍历，在遍历的过程中，逐个改变当前节点的指向。

  • 预先定义一个pre指针，指向当前节点的前一个节点。以及一个head指针指向头节点。
  • 当pre为空时，可以确定当前节点为双向链表的头节点head。其它情况下则可以将pre的后继指向当前节点cur。
  • 遍历过程中，对于每一个cur，都应将其前驱指向pre。同时不断跟新pre。最后返回head即可。

图解展示： alt

2.代码实现

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    //pre记录当前节点前一个，head记录头节点
    TreeNode pre=null,head=null;
    
    public TreeNode Convert(TreeNode pRootOfTree) {
        //为空判断
        if(pRootOfTree==null) return null;
        //递归
        dfs(pRootOfTree);
        return head;
        
    }
    
    private void dfs(TreeNode cur){
        //递归终止条件
        if(cur==null) return;
        //遍历左子树
        dfs(cur.left);
        //如果pre为空，说明当前是头节点
        if(pre==null) head=cur;
        //将pre的right指针指向cur
        else pre.right=cur;
        //将cur的left指针指向pre
        cur.left=pre;
        //更新pre
        pre=cur;
        //遍历右子树
        dfs(cur.right);
    }
}

3.复杂度分析

  • 时间复杂度：需要遍历二叉搜索树中每一个节点，所以时间复杂度为O(n)O(n)。
  • 空间复杂度：最坏情况下，递归栈深度为n，所以空间复杂度是O(n)O(n)。

方法二（迭代）

1.解题思路

同样需要借助中序遍历，访问到每一个节点，并改变节点的指向，这一点与方法一相同。不同的是借助栈来实现中序遍历，每次不断将节点压入栈中，并走到最后一个左子节点（由于栈是先进后出，所以能保证左子树节点在当前节点之前弹出），最后弹出的栈顶元素一定是中序遍历的当前节点，每弹出一个元素，都需要往右子树方向走（由于栈是先进后出，所以能保证右子树节点在当前节点之后弹出）。

2.代码实现

import java.util.LinkedList;

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    //pre记录当前节点前一个，head记录头节点
    TreeNode pre=null,head=null;
    //用于中序遍历
    LinkedList<TreeNode> stack=new LinkedList<>();
    
    public TreeNode Convert(TreeNode pRootOfTree) {
        //为空判断
        if(pRootOfTree==null) return null;
        //中序遍历
        inorder(pRootOfTree);
        return head;
        
    }
    
    //利用栈进行中序遍历
    private void inorder(TreeNode root){
        if(root==null) return;
        TreeNode node=root;
        while(!stack.isEmpty()||node!=null){
            //不断压栈，并走到最后一个左子节点
            if(node!=null){
                stack.push(node);
                node=node.left;
            }
            else{
                //此时弹出的是左子树最左节点（当前节点）
                node=stack.pop();
                //如果pre为空，说明当前是头节点
                if(pre==null) head=node;
                //将pre的right指针指向cur
                else pre.right=node;
                //将cur的left指针指向pre
                node.left=pre;
                //更新pre
                pre=node;
                node=node.right;
            }
        }
    }
}

3.复杂度分析

  • 时间复杂度：需要遍历二叉搜索树中每一个节点，所以时间复杂度为O(n)O(n)。
  • 空间复杂度：需要借助额外大小为n的栈来完成中序遍历，所以空间复杂度是O(n)O(n)。