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
给定一个二叉搜索树，要求更改每个节点的值为树中其它比他大的节点值之和。二叉搜索树的特点是中序遍历的结果为一个从小到大的序列。class Solution { int sum = 0; //全局变量 public TreeNode convertBST(TreeNode root) { if(root == null) return null; convertBST( root.right);//先右边 root.val += sum; sum = root.val; convertBST( root.left); return root; } }
538. Convert BST to Greater Tree
原文：http://www.cnblogs.com/wxshi/p/7598329.html