538. Convert BST to Greater Tree

538. 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

My Solutions:

因为是bst，较大的节点一定在右边，所以先去往树的右边找。

方法1：recursive

class Solution {
    
    int sum = 0;
    
    public TreeNode convertBST(TreeNode root) {
        
        if (root != null) {
            convertBST(root.right);
            sum += root.val;
            root.val = sum;
            convertBST(root.left);
        }
        return root;      
    }
}

方法2：iterative stack

//iterative
    public TreeNode convertBST(TreeNode root) {
        
        Stack<TreeNode> s = new Stack<>();
        TreeNode node = root;
        int sum = 0;
        while (!s.isEmpty() || node != null) {
            while (node != null) {
                s.add(node);
                node = node.right;
            }
            node = s.pop();
            sum += node.val;
            node.val = sum;
            node = node.left;
        }
        return root;
    }