[538. Convert BST to Greater Tree] #leetcode

538_0902.java

class Solution {
  // O(n) o(1)
    public TreeNode convertBST(TreeNode root) {
        dfs(root, new int[1]);
        return root;
    }
    
    private void dfs(TreeNode node, int[] sum) {
        if (node == null) return;
        dfs(node.right, sum);
        sum[0] += node.val;
        node.val = sum[0];
        dfs(node.left, sum);
    }
}

class Solution2 {
    public TreeNode convertBST(TreeNode root) {
        if (root == null) return null;
        int sum = 0;
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        TreeNode cur = root;
        while (!stack.isEmpty() || cur != null) {
            if (cur != null) {
                stack.add(cur);
                cur = cur.right;
            } else {
                cur = stack.removeLast();
                int tmp = cur.val;
                cur.val += sum;
                sum += tmp;
                cur = cur.left;
            }
        }
        
        return root;
    }
}