剑指 Offer II 052. 展平二叉搜索树

描述

给你一棵二叉搜索树，请你 按中序遍历 将其重新排列为一棵递增顺序搜索树，使树中最左边的节点成为树的根节点，并且每个节点没有左子节点，只有一个右子节点。

示例

示例1：

输入：root = [5,3,6,2,4,null,8,1,null,null,null,7,9]
输出：[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]

示例2：

输入：root = [5,1,7]
输出：[1,null,5,null,7]

提示

• 树中节点数的取值范围是 [1, 100]
• 0 <= Node.val <= 1000

解题思路

方法一：中序遍历之后生成新的树

• 先对输入的二叉搜索树执行中序遍历，将结果保存到一个列表中；
• 然后根据列表中的节点值，创建等价的只含有右节点的二叉搜索树，其过程等价于根据节点值创建一个链表。

代码

class Solution {
    List<Integer> list = new ArrayList<>();
    public TreeNode increasingBST(TreeNode root) {
        list = dfs(root);
        TreeNode first = new TreeNode(list.get(0));
        TreeNode pre = first;
        for (int i = 1; i < list.size(); i++) {
            TreeNode node = new TreeNode(list.get(i));
            pre.right = node;
            pre = node;
        }
        return first;
    }
    public List<Integer> dfs (TreeNode root) {
        if (root == null) return null;
        dfs(root.left);
        list.add(root.val);
        dfs(root.right);
        return list;
    }
}

复杂度分析

时间复杂度：O(n)，其中 n 是二叉搜索树的节点总数。
空间复杂度：O(n)，其中 n 是二叉搜索树的节点总数。需要长度为 n 的列表保存二叉搜索树的所有节点的值。

方法二：在中序遍历的过程中改变节点指向

当我们遍历到一个节点时，把它的左孩子设为空，并将其本身作为上一个遍历到的节点的右孩子。这里需要有一些想象能力。递归遍历的过程中，由于递归函数的调用栈保存了节点的引用，因此上述操作可以实现。

代码

class Solution {
    private TreeNode resNode;

    public TreeNode increasingBST(TreeNode root) {
        TreeNode dummyNode = new TreeNode(-1);
        resNode = dummyNode;
        inorder(root);
        return dummyNode.right;
    }

    public void inorder(TreeNode node) {
        if (node == null) {
            return;
        }
        inorder(node.left);

        // 在中序遍历的过程中修改节点指向
        resNode.right = node;
        node.left = null;
        resNode = node;

        inorder(node.right);
    }
}

复杂度分析

• 时间复杂度：O(n)，其中 n 是二叉搜索树的节点总数。
• 空间复杂度：O(n)。递归过程中的栈空间开销为 O(n)。