# Convert BST to Greater Tree

[https://leetcode.com/problems/convert-bst-to-greater-tree/description/](https://leetcode.com/problems/convert-bst-to-greater-tree/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.

## Thoughts

要利用到BST inorder traversal的结果是排好序的。\
left->当前->right是升序，right->当前->left是降序。\
我们因此可以在用sum存储访问到当前结点时总和是多少。

## Code

```
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private int convert(TreeNode node, int sum) {
        if (node == null) {
            return sum;
        }
        sum = convert(node.right, sum);
        node.val += sum;
        sum = node.val;
        sum = convert(node.left, sum);
        return sum;
    }

    public TreeNode convertBST(TreeNode root) {     
        convert(root, 0);
        return root;
    }
}
```

## Analysis

时间复杂度和遍历一样是O(n)

## Ver.2

用栈实现右中左的中序遍历.

```
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private void pushRight(Stack<TreeNode> stack, TreeNode node) {
        while (node != null) {
            stack.push(node);
            node = node.right;
        }
    }

    public TreeNode convertBST(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        pushRight(stack, root);
        int sum = 0;
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            sum += node.val;
            node.val = sum;
            pushRight(stack, node.left);
        }

        return root;
    }
}
```
