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. Let’s Convert BST to Greater Tree.
Example:
Input: The root of a Binary Search Tree like this:
5
/ \
2 13
5
/ \
2 13
Output: The root of a Greater Tree like this:
18
/ \
20 13
Approach 1: Using Reversed inorder traversal.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode convertBST(TreeNode root) {
if(root==null){
return root;
}else{
DFS (root,0);
}
return root;
}
public int DFS(TreeNode root, int presum){
if(root.right!=null){
presum=DFS(root.right,presum);
}
root.val+=presum;
return (root.left!=null?DFS(root.left,root.val):root.val);
}
}
Best Approach:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
int sum=0;
public TreeNode convertBST(TreeNode root) {
helper(root);
return root;
}
public void helper(TreeNode root){
if(root==null)return;
helper(root.right);
sum=sum+root.val;
root.val=sum;
helper(root.left);
}
}