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
Solution: 因为每个node要把大于它的值相加,所以可以按descending order遍历,所以用reverse in-order遍历。
int sum = 0;
public TreeNode convertBST(TreeNode root) {
helper(root);
return root;
}
private void helper(TreeNode root) {
if (root == null) {
return;
}
helper(root.right);
root.val += sum;
sum = root.val;
helper(root.left);
}