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 条评论
登录 后参与评论

相关文章

来自专栏张善友的专栏

更新Silverlight ctp到Silverlight beta 1.0

下面是我更新Silverlight ctp到Silverlight beta 1.0的一个纪录,希望对各位同学有帮助。 1、卸载Silverlight ctp ...

1759
来自专栏张善友的专栏

How does it work in Mono's C# compiler?

Introduction Mono is an Open Source free programming language project. It is an ...

2777
来自专栏Albert陈凯

2018-11-06 openhub.net开源项目。

762
来自专栏walterlv - 吕毅的博客

Reading the Source Code of Microsoft.NET.Sdk, Writing the Creative Extension of Compiling

发布于 2018-06-30 12:27 更新于 2018-08...

612
来自专栏前端小叙

网页CSS常用中英文字体收集

Windows的中文字体: 黑体:SimHei 宋体:SimSun 新宋体:NSimSun 仿宋:FangSong 楷体:KaiTi 仿宋_GB2312:Fan...

2824
来自专栏我和未来有约会

(收藏)搭建.NET Framework 3.0开发环境 及SharePoint 2007/WSS 3环境

第一步:首先您必须安装.NET Framework 3.0,则可以下载其Redistributable Package Microsoft .NET Frame...

1846
来自专栏码匠的流水账

使用webflux提升数据导出效率

两种方法目前看来用时差不多,不过后者可以避免超时。当然使用传统mvc也可以实现类似效果,就是拿到response的输出流不断地write和flush。不过web...

1912
来自专栏张善友的专栏

每周.NET前沿技术文章摘要(2017-05-17)

汇总国外.NET社区相关文章,覆盖.NET ,ASP.NET等内容: .NET .NET Framework 4.7正式发布 链接: http://www....

1756
来自专栏张善友的专栏

Firebird 数据库资源

Firebird is a database with 20 years of history, full set of features (including...

2278
来自专栏张善友的专栏

IbatisNet支持2.0的版本Release 发布了

iBATIS.NET DataMapper 1.5 and DataAccess 1.8 Beta! (Jul 5, 2006) The iBATIS.NET ...

17710

扫码关注云+社区