Convert BST to Greater Tree

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

Tips:

Recursion的做法需要注意先sum += root.val，然后root = sum，不然会root值出错。

Code：

Recursive:

public class Solution {
    int sum = 0;
    public TreeNode convertBST(TreeNode root) {
        helper(root);
        return root;        
    }

    private void helper(TreeNode root) {
        if (root == null) return;
        helper(root.right);
        sum += root.val;
        root.val = sum;
        helper(root.left);        
    }
}

Stack:

public class Solution {
    public TreeNode convertBST(TreeNode root) {
        int sum = 0;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;
        while (!stack.isEmpty() || node != null) {
            while (node != null) {
                stack.push(node);
                sum += node.val;
                node = node.left;
            }
            node = stack.pop();
            node = node.right;
        }
        int sum1 = 0;
        stack = new Stack<>();
        node = root;
        while (!stack.isEmpty() || node != null) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            int temp = node.val;
            node.val = sum - sum1;
            sum1 += temp;
            node = node.right;
        }
        return root;
    }
}