Convert BST to Greater Tree

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