leetcode538 Convert BST to Greater Tree

题目

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 简单来说，就是把一棵BST的所有节点的值转化为其本身加上所有比它的节点的和。

解题思路

当看到这个题目的时候，我是懵逼的。很明显存在重复计算和，所以我一开始想的是动态规划，然后我花了一个图。

这里写图片描述

红色代表节点应该被访问的顺序，定睛一看，这似乎和中序遍历差不多啊。只不过中序遍历是左中右，而这里是右中左而已。 为了追求效率，采取非递归的遍历，设置一个值保存之前的和。

public class leetcode538 {
    public TreeNode convertBST(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode p = root;
        int res = 0;
        while (!stack.isEmpty()||p!=null){
            if(p!=null) {
                stack.push(p);
                p = p.right;
            }
            else {
                p = stack.pop();
                int temp = p.val;
                p.val += res;
                res += temp;
                p = p.left;
            }
        }
        return root;
    }
}