538 Convert BST to Greater Tree

538. Convert BST to Greater Tree

1. Question

Given a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST.

Example:

Input:
 The root of a Binary Search Tree like this:
              5
            /   \
           2     13


Output:
 The root of a Greater Tree like this:
             18
            /   \
          20     13

2. Implementation

(1) Recursion

思路：首先处理right children， 然后当前的node，最后才是leftChildren，维护一个变量sum记录当前所得到的和。

class Solution {
    public TreeNode convertBST(TreeNode root) {
        getSum(root, 0);
        return root;
    }

    public int getSum(TreeNode node, int sum) {
        if (node == null) {
            return sum;
        }

        int rightSum = getSum(node.right, sum);
        node.val += rightSum;
        int leftSum = getSum(node.left, node.val);
        return leftSum;
    }
}

(2) Iteration

思路：迭代的做法和inorder traversal很像，不同在于我们先从right children遍历，然后是当前的node, 最后才是left children，和inorder traversal正好相反

class Solution {
    public TreeNode convertBST(TreeNode root) {
        if (root == null) {
            return null;
        }

        Stack<TreeNode> stack = new Stack<>();
        int sum = 0;
        TreeNode curNode = root;

        while (curNode != null || !stack.isEmpty()) {
            if (curNode != null) {
                stack.push(curNode);
                curNode = curNode.right;
            }
            else {
                curNode = stack.pop();
                curNode.val += sum;
                sum = curNode.val;
                curNode = curNode.left;
            }
        }
        return root;
    }
}

3. Time & Space Complexity

Recursion: 时间复杂度:O(n), 空间复杂度:O(h), h为树的高度

Iteration: 时间复杂度: O(n), 空间复杂度: O(n)