@@ -0,0 +1,1332 @@
+package fundamentals.tree.dfs.inorder.lc538_convertbsttogreatertree;%0A%0Aimport fundamentals.tree.TreeNode;%0A%0A/**%0A * Given a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to%0A * the original key plus sum of all keys greater than the original key in BST.%0A */%0Apublic class Solution %7B%0A%0A    public TreeNode convertBST(TreeNode root) %7B%0A        dfs(root, 0);%0A        return root;%0A    %7D%0A%0A    // Simple to think from reversed inorder traversal view%0A    // sum   : all nodes which we have traversed thus far%0A    // return: root.val + sum of all nodes greater than root%0A    private int dfs(TreeNode root, int sum) %7B%0A        if (root == null) return sum;%0A        int rsum = dfs(root.right, sum);%0A        root.val += rsum;%0A        return dfs(root.left, root.val);%0A    %7D%0A%0A    /**    A%0A     *   /   %5C%0A     *  X    ...%0A     * /%5C%0A     * L R%0A     *%0A     * sum = sum of A.val and right subtree%0A     * R += sum%0A     * X += sum + rsum%0A     * L += sum + X.val + rsum%0A     * Return sum of all nodes of current tree%0A     */%0A    private int dfs_my(TreeNode root, int sum) %7B%0A        if (root == null) return 0;%0A        int rsum = dfs(root.right, sum);%0A        int oval = root.val;%0A        root.val += sum + rsum;%0A        int lsum = dfs(root.left, root.val);%0A        return oval + lsum + rsum;%0A    %7D%0A%0A%7D%0A

convert BST to greater tree