分析

• 本题的考点：二叉树的中序遍历。

• 关于树的遍历可以参考网址：树的遍历。

• 本题提供两种解法。

方法1

• 分为两步：（1）将中序遍历结果存入数组中；（2）根据中序遍历结果构建增顺序搜索树。

• 这种方式会创建新的节点，没有利用原树中的节点。该方法使用C++实现。

方法2

• 直接对原树进行操作，改变原树的指针。使用一个全局变量preNode记录当前节点node的前一个节点。并使用虚拟头结点dummy的rigth指针记录新树的头结点，我们只需要在第一次遍历到原树中最左节点记录下来即可。

• 这种方法使用Java实现。

代码

• C++

class Solution {
public:
    TreeNode* increasingBST(TreeNode* root) {

        // (1) 将中序遍历结果存入数组中
        vector<int> nums;
        stack<TreeNode *> stk;
        while (root || stk.size()) {
            while (root) {
                stk.push(root);
                root = root->left;
            }
            root = stk.top(); stk.pop();
            nums.push_back(root->val);
            root = root->right;
        }
        // (2) 根据中序遍历结果构建增顺序搜索树
        auto dummy = new TreeNode(-1), cur = dummy;
        for (int i = 0; i < nums.size(); i++) {
            cur->right = new TreeNode(nums[i]);
            cur = cur->right;
        }
        return dummy->right;
    }
};

• Java

class Solution {

    TreeNode preNode = new TreeNode(-1);

    public TreeNode increasingBST(TreeNode root) {

        TreeNode dummy = new TreeNode(-1);  // 虚拟头结点
        preNode = dummy;
        dfs(root);
        return dummy.right;
    }

    private void dfs(TreeNode node) {

        if (node == null) return;

        dfs(node.left);

        preNode.right = node;  // 第一次执行这句话时, preNode就是dummy, 会让dummy.right指向新树头结点
        node.left = null;
        preNode = node;  // 之后preNode会被重新赋值，preNode != dummy

        dfs(node.right);
    }
}

时空复杂度分析

• 时间复杂度：$O(n)$，n是树中的节点数。

• 空间复杂度：$O(h)$，h是树高。递归会使用到系统栈，非递归会使用自己创建的栈。