Java 求解如何把二叉搜索树转换为累加树
作者:南淮北安 发布时间:2021-11-19 14:09:54
标签:Java,二叉搜索树,累加树
一、题目
给出二叉搜索树的根节点,该树的节点值各不相同,请你将其转换为累加树(Greater Sum Tree),使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
提醒一下,二叉搜索树满足下列约束条件:
节点的左子树仅包含键 小于 节点键的节点。
节点的右子树仅包含键 大于 节点键的节点。
左右子树也必须是二叉搜索树。
二、题解
观察示例图发现,树的遍历顺序为右,中,左的顺序,每个节点的值,是按照这个顺序累加的状态
由于是需要累加,所以需要pre指针记录当前遍历节点cur的前一个节点,方便累加
(1)确定递归函数及返回值
题目需要遍历整棵树,同时需要定义一个全局变量 pre,用来保存 cur节点的前一个节点的数值
(2)确定递归终止条件
遇到空就终止
(3)确定单层递归的逻辑
遍历的顺序,右,中,左
三、代码
class Solution {
// 记录前驱节点
int pre = 0;
public TreeNode convertBST(TreeNode root) {
// 空节点终止
if (root == null) {
return root;
}
// 遍历顺序:右,中,左
convertBST(root.right);
root.val += pre;
pre = root.val;
convertBST(root.left);
return root;
}
}
四、总结
观察示例节点的规律,需要记录上个节点的情况,注意引入前驱节点pre
来源:https://blog.csdn.net/nanhuaibeian/article/details/121096863
0
投稿
猜你喜欢
- 前言上文讲的MyBatis部署运行且根据官网运行了一个demo:一步到位部署运行MyBatis3源码<保姆级>jdbc再贴一个J
- 最近要做一个网站,要求实现验证码程序,经过不断调试,终于成功实现功能。一、验证码生成类生成验证码的话需要用到java的Graphics类库,
- 自定义工具类PropertyUtil,并在该类的static静态代码块中读取properties文件内容保存在static属性中以供别的程序
- 在使用springMVC框架构建web应用,客户端常会请求字符串、整型、json等格式的数据,通常使用@ResponseBody注解使 co
- 随着C语言的学习慢慢结束,博主也要开始学习一门新语言了,那就是java。所以博主将会开启一个新的关于java的专栏,所以想要慢慢和我一起学习
- 源程序揭秘杨辉三角形性质: 每行数字左右对称,由 1 开始逐渐变大,然后变小,回到 1。 第 n 行的数字个数为 n 个。 第 n 行数字和
- idea spring Initializr创建项目勾选项目所需要的依赖pom.xml文件会加载勾选的依赖,也可以不勾选后面通过自己常用的p
- 前言在原生的 Android 或 iOS 中,都提供了基本的键值对存储方式,Android 是 SharedPreferences,iOS
- 业务现象代码中有一部分代码多次嵌套循环和数据处理,执行速度很慢解决方案通过多线程1、启用多线程private final static Ex
- 1.需求背景需要实现一个动态加载但不显示出来的视图,且该视图上有个动态生成的二维码,最后用其去生成一张快照(也就是图片)。(常见这种情况是来
- 前言本篇文章 中写到的是 flutter 调用了Android 原生的 TextView 案例添加原生组件的流程基本上可以描述为:1 and
- IDEA SpringBoot项目配置热更新的步骤1.在pom.xml中添加依赖:<dependency><groupId
- 背景SpringBoot 版本<parent> <groupId>org.springfr
- 目录一、图示二、链表的概念及结构三、单链表的实现四、完整代码的展示一、图示二、链表的概念及结构 链表是一种物理存储结构上非连续存储结构,数据
- 本文实例讲述了Android编程实现WebView添加进度条的方法。分享给大家供大家参考,具体如下:标准的XML界面<?xml ver
- 日常对于金额计算,应该都是用的BigDecimal,可是苦于没有好的工具类方法,现在贡献一个我正在用的对于数字计算的工具类,项目中就是用的这
- 目录一:spring读取配置或注解的过程二:spring的bean的生命周期2.1:实例化 Instantiation2.2:初始化3: 使
- @ConditionalOnProperty作用及用法在spring boot中有时候需要控制配置类是否生效,可以使用@Conditiona
- 1.try-catch异常处理说明Java提供try和catch块来处理异常,try块用于包含可能出错的代码。catch块用于处理try块中
- Mybatis typeAlias配置1.定义别名<typeAliases> <ty