题解 | #二叉搜索树与双向链表#

这道题可以看做是 BM24中序遍历（迭代法）的变体
其实仔细想想，用迭代反而能更容易得写出来

迭代法求解

public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree==null) return null;
        TreeNode hair = new TreeNode();
        // 免去 head == null 的判断
        TreeNode tail = hair;
        // 中序遍历（迭代）
        Deque stack = new LinkedList();
        TreeNode curr = pRootOfTree;
        while (curr!=null || !stack.isEmpty()) {
            while (curr!=null) {
                stack.offerLast(curr);
                curr = curr.left;
            }
            curr = stack.pollLast();
            tail.right = curr;
            curr.left = tail;
            tail = tail.right;
            curr = curr.right;
        }
        // 卸磨杀驴
        TreeNode head = hair.right;
        hair.right = null;
        head.left = null;
        return head;
    }

递归法求解

当然，用递归也不是写不出来，就是因为 Java 因为没有引用变量
所以必须带一个全局变量，记录当前双向列表的尾部位置

// 全局变量
    private TreeNode tail = null;
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree==null) return null;
        TreeNode hair = new TreeNode();
        tail = hair;
        dfs(pRootOfTree);
        TreeNode head = hair.right;
        hair.right = null;
        head.left = null;
        return head;
    }

    private void dfs(TreeNode root) {
        if (root.left==null && root.right==null) {
            tail.right = root;
            root.left = tail;
            // tail 作为局部变量，其修改是不会带到其他函数里的！！
            tail = tail.right;
            return;
        }
        if (root.left!=null) {
            dfs(root.left);
        }
        tail.right = root;
        root.left = tail;
        tail = tail.right;
        if (root.right!=null) {
            dfs(root.right);
        }
    }

如果对迭代法的辅助栈的空间忽略不计（因为Deque的实现用的 LinkedList，没有额外创建新的对象，所以辅助栈确实可以忽略不计）
那么两种方法的空间复杂度都是 O(1)，时间复杂度都是 O(N)
但是，用迭代法，思路更加清晰，不容易出错，还不需要开全局变量
所以对于这道题，明显是迭代法更胜一筹