Description
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:
BST
Output: The root of a Greater Tree like this:
Greater tree
Solution
DFS, time O(n), space O(1)
对于每个节点，node.val += sum(all nodes val on the right)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode convertBST(TreeNode root) {
convertBSTHelper(root, 0);
return root;
}
public int convertBSTHelper(TreeNode root, int sum) {
if (root == null) {
return sum;
}
root.val += convertBSTHelper(root.right, sum);
return convertBSTHelper(root.left, root.val);
}
}
