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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

扫码关注云+社区