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);
    }

results matching ""

    No results matching ""