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

Given a binary search Tree ｀{5,2,3}｀:

              5
            /   
           2     13

Return the root of new tree

             18
            /   
          20     13

逆中序遍历树，注意root的greatSum是input greatSum和右子树sum的和；输入给左子树的greatSum 是root.val

 1 /**
 2  * Definition of TreeNode:
 3  * public class TreeNode {
 4  *     public int val;
 5  *     public TreeNode left, right;
 6  *     public TreeNode(int val) {
 7  *         this.val = val;
 8  *         this.left = this.right = null;
 9  *     }
10  * }
11  */
12 public class Solution {
13     /**
14      * @param root the root of binary tree
15      * @return the new root
16      */
17     public TreeNode convertBST(TreeNode root) {
18         // Write your code here
19         if (root == null) {
20             return root;
21         }
22         helper(root, 0);
23         return root;
24     }
25     private int helper(TreeNode root, int greatSum){
26         int sum = 0;
27         if (root.right != null) {
28             sum += helper(root.right, greatSum);
29         }
30         int temp = greatSum + sum;
31         sum += root.val;
32         root.val += temp;
33         if (root.left != null) {
34             sum += helper(root.left, root.val);
35         }
36         return sum;
37     }
38 }