[LeetCode] Problem 538 - Convert BST to Greater Tree

Posted on | In ,

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:

1
2
3
   5
 /   \
2     13

Output: The root of a Greater Tree like this:

1
2
3
   18
  /   \
20     13

Code

1
2
3
4
5
6
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private int sum = 0;

public TreeNode convertBST(TreeNode root) {
    if (root == null)
        return null;

    if (root.right != null)
        convertBST(root.right);

    sum += root.val;
    root.val = sum;

    if (root.left != null)
        convertBST(root.left);

    return root;
}