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
投稿猜你喜欢
游戏界面程序代码using System;using System.Collections.Generic;using System.Com- C#中的null与SQL中的NULL是不一样的，SQL中的NULL用C#表示出来就是DBNull.Value。注意：SQL参数是不能接受C#
- 在maven中有几种方法打包项目，在之前的一篇博客中【Java】打包Jar包并用脚本执行，已经介绍了怎么在没有maven插件的情况下，怎么打
- 1 pom.xml文件注：热部署功能spring-boot-1.3开始有的<!--添加依赖--><dependency&g
- switch语句的格式如下：（它的功能是选出一段代码执行） switch(整数选择因子) { case 整数值1 : 语句; break;
- 前言《JAVA打砖块》游戏是自制的游戏。玩家操作一根萤幕上水平的“棒子”，让一颗不断弹来弹去的&am
- jrebelJRebel是一套JavaEE开发工具。JRebel允许开发团队在有限的时间内完成更多的任务修正更多的问题，发布更高质量的软件产
- 一个activity就好比一个网页，此文章讲解怎样创建一个activity并且实现跳转！一、学习创建Activity1、新建一个java类，
- onclick事件的定义方法，分为三种，分别为在xml中进行指定方法；在Actitivy中new出一个OnClickListenner()；
- GridView是类似于ListView的控件，只是GridView可以使用多个列来呈现内容，而ListView是以行为单位，所以用法上是差
- 本文实例讲述了Android开发之多媒体文件获取工具类。分享给大家供大家参考，具体如下：package com.android.ocr.ut
- c#开发cad如何预览图块1.定义变量的方法代码如下2. 获取GetDwgImag图像的方法代码3.实现显示DWG文件的方法代码方
- 实践过程效果代码public partial class Form1 : Form{ public Form1()
- PROPAGATION_REQUIRED: 如果存在一个事务，则支持当前事务。如果没有事务则开启事务；PROPAGATION_REQUIRE
- 在看KMP算法时,想要简单的统计一下执行时间和性能。得出的结论是： Java的String的indexOf方法性能最好，其次是KMP算法，其
- 类是使用关键字 class 声明的，如下面的示例所示：访问修饰符 class 类名 { //类成员： // Methods, prope
- 一般表单数据分为两类<form method="post" action="${pageContext.
- 我们在j2ee当中，连接数据库的时候经常会用到properties配置文件，我们原来在eclipse或者myeclipse当中会在src文件
- 在windows环境下进行的测试，前提条件，windows上需要先安装openssl。配置环境变量，查看版本：import java.io.
- 在 fluro 中，定义路由处理器 Handler 时可以指定该页面的默认转场形式，或者在使用 navigateTo 方法是可以设置页面跳转
