转载----
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 13Output: The root of a Greater Tree like this: 18 / \ 20 13
题目标题：Tree
这道题目给了我们一个二叉搜索树，特性是 left < root < right 对于每一个点。基于这个特性，如果我们要把 每一个点的值 变成 所有比这个点大的sum 再加上它自己，这样的话，我们必须从最右边底下的点开始遍历，因为它是最大的点。设一个sum，利用inorder 来遍历tree， 每次当一个点，它的右边点返回之后，更新sum的值， 用sum = sum + 这个点的val。再把这个点的值更新 = sum。所以根据这个顺序，我们看一下原题给的例子，利用inorder 顺序，结合 right root left 顺序， 我们先一直走到最右边底的点，13， 13右边返回的null， 然后sum = 0 + 13, 13这个点的值就等于sum(13)，再去left，这个left返回的也是null。 接着13返回到5这个点， 5的右边点是13， 那么sum = 13+5 (18) 5这个点就更新为18。再去left， 2这个点，2的右边返回的是null， 然后sum = 18 + 2 (20), 再去2的left，null。最后返回到root。
Java Solution:
Runtime beats 89.45%
完成日期：07/07/2017
关键词：Tree
关键点：inorder 来遍历树； 每个点顺序是right， root， left
1 /** 2 * Definition for a binary tree node. 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9 */10 public class Solution 11 {12 int sum = 0;13 public TreeNode convertBST(TreeNode root) 14 {15 if(root == null)16 return null;17 18 convertBST(root.right);19 20 sum += root.val;21 root.val = sum;22 23 convertBST(root.left);24 25 return root;26 }27 } 