题目
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.
答案
用global variable accumulate current sum, traverse in reversed order
class Solution {
int sum = 0;
public TreeNode convertBST(TreeNode root) {
recur(root);
return root;
}
// Just traverse the tree in reverse order, and add
public void recur(TreeNode root) {
if(root == null) return;
// go right
recur(root.right);
root.val = root.val + sum;
sum = root.val;
// go left
recur(root.left);
}
}
without global variable:
class Solution {
public TreeNode convertBST(TreeNode root) {
recur(root, 0);
return root;
}
// Just traverse the tree in reverse order, and accumulate the sum using return value
public int recur(TreeNode root, int sum) {
if(root == null) return sum;
// go right
int right = recur(root.right, sum);
root.val = root.val + right;
// go left
int left = recur(root.left, root.val);
return left;
}
}
