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.

答案
用global variable accumulate current sum, traverse in reversed order

class Solution {
    int sum = 0;
    
    public TreeNode convertBST(TreeNode root) {
        recur(root);
        return root;
    }
    
    // Just traverse the tree in reverse order, and add
    public void recur(TreeNode root) {
        if(root == null) return;
        
        // go right
        recur(root.right);
        root.val = root.val + sum;
        sum = root.val;
        // go left
        recur(root.left);
    }
}

without global variable:

class Solution {
    public TreeNode convertBST(TreeNode root) {
        recur(root, 0);
        return root;
    }
    
    // Just traverse the tree in reverse order, and accumulate the sum using return value
    public int recur(TreeNode root, int sum) {
        if(root == null) return sum;
        
        // go right
        int right = recur(root.right, sum);
        root.val = root.val + right;
        
        // go left
        int left = recur(root.left, root.val);
        return left;
    }
}