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
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
public class Solution {
/**
* @param root the root of binary tree
* @return the new root
*/
public TreeNode convertBST(TreeNode root) {
// Write your code here
if (root == null) {
return root;
}
helper(root, 0);
return root;
}
private int helper(TreeNode root, int greatSum){
int sum = 0;
if (root.right != null) {
sum += helper(root.right, greatSum);
}
int temp = greatSum + sum;
sum += root.val;
root.val += temp;
if (root.left != null) {
sum += helper(root.left, root.val);
}
return sum;
}
}