当前位置: 首页 > news >正文

LeetCode538. 把二叉搜索树转换为累加树

538. 把二叉搜索树转换为累加树

文章目录

      • [538. 把二叉搜索树转换为累加树](https://leetcode.cn/problems/convert-bst-to-greater-tree/)
        • 一、题目
        • 二、题解
          • 方法一:递归(中序遍历与节点更新)
          • 方法二:反向中序遍历与累加更新:更简洁的解法
          • 方法三:迭代(反向中序遍历)


一、题目

给出二叉 搜索 树的根节点,该树的节点值各不相同,请你将其转换为累加树(Greater Sum Tree),使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

提醒一下,二叉搜索树满足下列约束条件:

  • 节点的左子树仅包含键 小于 节点键的节点。
  • 节点的右子树仅包含键 大于 节点键的节点。
  • 左右子树也必须是二叉搜索树。

示例 1:

img

输入:[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
输出:[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

示例 2:

输入:root = [0,null,1]
输出:[1,null,1]

示例 3:

输入:root = [1,0,2]
输出:[3,3,2]

示例 4:

输入:root = [3,2,4,1]
输出:[7,9,4,10]

提示:

  • 树中的节点数介于 0104 之间。
  • 每个节点的值介于 -104104 之间。
  • 树中的所有值 互不相同
  • 给定的树为二叉搜索树。

二、题解

方法一:递归(中序遍历与节点更新)

针对这个问题,我们可以考虑通过中序遍历来获取有序的节点值,然后从大到小更新节点的值,以满足累加树的要求。

算法思路

  1. 创建一个空的向量 array 用于存储中序遍历得到的有序节点值。

  2. 执行中序遍历函数 traversal_vec(root, array),该函数会将二叉搜索树的节点值按照从小到大的顺序存储在 array 中。

  3. array 的倒数第二个元素开始,将每个元素与其后一个元素相加,以便得到累加和。这一步保证了在累加树中,每个节点的值等于原树中大于或等于该节点值的所有节点值之和。

  4. 执行函数 traversal_res(root, array),该函数会将更新后的累加和值赋给二叉搜索树的每个节点。

  5. 返回更新后的二叉搜索树。

具体实现

以下是对每个步骤的详细实现:

class Solution {
public:int i = 0;// 中序遍历获取有序节点值并存储在array中void traversal_vec(TreeNode *root, vector<int> &array){if(root == nullptr) return;traversal_vec(root->left, array);array.push_back(root->val);traversal_vec(root->right, array);}// 更新节点值为累加和void traversal_res(TreeNode *root, vector<int>& array){if(root == nullptr) return;traversal_res(root->left, array);root->val = array[i++];traversal_res(root->right, array);}TreeNode* convertBST(TreeNode* root) {if(root == nullptr) return nullptr;vector<int> array;// 获取有序节点值traversal_vec(root, array);// 计算累加和for(int j = array.size() - 2; j >= 0; j--){array[j] += array[j+1];}// 更新节点值为累加和traversal_res(root, array);return root;}
};

或者将i作为参数传入traversal_res()也行:

class Solution {
public:void traversal_vec(TreeNode *root, vector<int> &array) {if (root == nullptr) return;traversal_vec(root->left, array);array.push_back(root->val);traversal_vec(root->right, array);}int traversal_res(TreeNode *root, int i, const vector<int> &array) {if (root == nullptr) return i;i = traversal_res(root->left, i, array);root->val = array[i];i++;i = traversal_res(root->right, i, array);return i;}TreeNode* convertBST(TreeNode* root) {if (root == nullptr) return nullptr;vector<int> array;traversal_vec(root, array);for (int j = array.size() - 2; j >= 0; j--) {array[j] += array[j + 1];}traversal_res(root, 0, array);return root;}
};

算法分析

  • 时间复杂度:算法的时间复杂度主要由两个部分构成:中序遍历和更新节点值。中序遍历需要访问每个节点一次,而更新节点值也需要访问每个节点一次。因此,算法的时间复杂度为 O(N),其中 N 是节点的数量。

  • 空间复杂度:算法的空间复杂度主要由中序遍历时存储节点值的数组 array 所占用的空间。在最坏的情况下,数组的大小为 N,因此空间复杂度为 O(N)。除此之外,递归调用栈也会占用一些空间,但是在二叉搜索树的情况下,递归调用栈的最大深度不会超过树的高度,因此额外空间的使用不会超过 O(log N)。

方法二:反向中序遍历与累加更新:更简洁的解法

算法思路

这个算法采用了一种不同的方法来实现二叉搜索树到累加树的转换。通过反向中序遍历(从右子树到左子树),我们可以更方便地得到大于当前节点值的节点值之和,然后直接更新节点值,从而获得累加树。

具体实现

class Solution {
public:// 反向中序遍历并更新节点值void convertBSTHelper(TreeNode* root, int& sum) {if(root == nullptr) return;convertBSTHelper(root->right, sum); // 先处理右子树sum += root->val; // 更新累加和root->val = sum; // 更新节点值convertBSTHelper(root->left, sum); // 处理左子树}TreeNode* convertBST(TreeNode* root) {if(root == nullptr) return nullptr;int sum = 0;convertBSTHelper(root, sum);return root;}
};

算法分析

  • 时间复杂度:算法的时间复杂度主要由中序遍历和更新节点值组成。每个节点都会被访问一次且只访问一次,因此时间复杂度为 O(N),其中 N 是节点的数量。
  • 空间复杂度:算法的空间复杂度由递归调用栈所占用的空间决定。在二叉搜索树的情况下,递归调用栈的最大深度不会超过树的高度,因此额外空间的使用不会超过 O(log N)。
方法三:迭代(反向中序遍历)

算法思路

这个算法采用了反向中序遍历的方式,通过栈来实现,来构建累加树。遍历的过程中,我们从最大值开始,逐步向较小值移动,同时将大于等于当前节点值的所有节点值累加起来,然后将该累加值赋予当前节点,最终构建出累加树。

具体实现

class Solution {
private:int previousValue; // 记录前一个节点的值// 反向中序遍历并更新节点值void reverseInorderTraversal(TreeNode* root) {stack<TreeNode*> nodeStack;TreeNode* current = root;while (current != nullptr || !nodeStack.empty()) {if (current != nullptr) {nodeStack.push(current);current = current->right; // 右子树} else {current = nodeStack.top(); // 弹出栈顶节点nodeStack.pop();// 更新节点值current->val += previousValue;previousValue = current->val;current = current->left; // 左子树}}}public:TreeNode* convertBST(TreeNode* root) {previousValue = 0; // 初始化前一个节点的值reverseInorderTraversal(root); // 反向中序遍历更新节点值return root;}
};

算法分析

  • 时间复杂度:算法的时间复杂度主要由反向中序遍历过程构成。每个节点会被访问一次且只访问一次,因此时间复杂度为 O(N),其中 N 是节点的数量。

  • 空间复杂度:算法的空间复杂度由栈所占用的空间决定。在最坏情况下,栈的大小可能达到树的高度,即 O(log N)。

相关文章:

LeetCode538. 把二叉搜索树转换为累加树

538. 把二叉搜索树转换为累加树 文章目录 [538. 把二叉搜索树转换为累加树](https://leetcode.cn/problems/convert-bst-to-greater-tree/)一、题目二、题解方法一&#xff1a;递归&#xff08;中序遍历与节点更新&#xff09;方法二&#xff1a;反向中序遍历与累加更新&#x…...

TP6 使用闭合语句查询多个or的模型语句

例子&#xff1a;查询出在单位表中所有的小学&#xff0c;初中和高中&#xff1b;其中school_period保存的就是学段数据$where []; $where[] function ($query) {$query->where(school_period, like, %小学%)->whereOr(school_period, like, %初中%)->whereOr(schoo…...

浅析Linux SCSI子系统:设备管理

文章目录 概述设备管理数据结构scsi_host_template&#xff1a;SCSI主机适配器模板scsi_host&#xff1a;SCSI主机适配器主机适配器支持DIF scsi_target&#xff1a;SCSI目标节点scsi_device&#xff1a;SCSI设备 添加主机适配器构建sysfs目录 添加SCSI设备挂载LunIO请求队列初…...

爬虫逆向实战(二十五)--某矿采购公告

一、数据接口分析 主页地址&#xff1a;某矿 1、抓包 通过抓包可以发现数据接口是cgxj/by-lx-page 2、判断是否有加密参数 请求参数是否加密&#xff1f; 通过查看“载荷”模块可以发现有一个param的加密参数 请求头是否加密&#xff1f; 无响应是否加密&#xff1f; 无c…...

DPLL 算法之分裂策略

前言 DPLL算法确实是基于树&#xff08;或二叉树&#xff09;的回溯搜索算法&#xff0c;它用于解决布尔可满足性问题&#xff08;SAT问题&#xff09;。下面我会分析您提到的DPLL算法中的分裂策略&#xff0c;以及它是如何在搜索过程中起作用的。 DPLL算法中的分裂策略是用于在…...

Jmeter+ServerAgent

一、Jmeter 下载 https://jmeter.apache.org/download_jmeter.cgi选择Binaries二进制下载 apache-jmeter-5.6.2.tgz 修改配置文件 jmeter下的bin目录&#xff0c;打开jmeter.properties 文件 languagezh_CN启动命令 cd apache-jmeter-5.6/bin sh jmeter二、ServerAgent 监…...

打破数据孤岛!时序数据库 TDengine 与创意物联感知平台完成兼容性互认

新型物联网实现良好建设的第一要务就是打破信息孤岛&#xff0c;将数据汇聚在平台统一处理&#xff0c;实现数据共享&#xff0c;放大物联终端的行业价值&#xff0c;实现系统开放性&#xff0c;以此营造丰富的行业应用环境。在此背景下&#xff0c;物联感知平台应运而生&#…...

ubuntu22安装和部署Kettle8.2

前提 kettle是纯java编写的etl开源工具&#xff0c;目前kettle7和kettle8都需要java8或者以上才能正常运行。所以运行kettle前先检查java环境是否正确配置&#xff0c;java版本是否是8或者以上。 kettle安装 1、创建kettle目录&#xff0c;并将kettle的zip包解压到kettle目…...

修复 Ubuntu Linux 中的“找不到命令‘python’”错误

在ubuntu 22.04版本中使用 callstack backtrace.txt 回溯错误点是碰到了该问题。 参考文章&#xff1a;链接 ubuntu22.04版本中默认只安装了python3版本 查看python各个版本安装情况&#xff0c;在终端输入命令&#xff1a; type python python2 python3如果安装了对应的版本…...

【业务功能篇86】微服务-springcloud-系统性能压力测试-jmeter-性能优化-JVM参数调优

系统性能压力测试 一、压力测试 压力测试是给软件不断加压&#xff0c;强制其在极限的情况下运行&#xff0c;观察它可以运行到何种程度&#xff0c;从而发现性能缺陷&#xff0c;是通过搭建与实际环境相似的测试环境&#xff0c;通过测试程序在同一时间内或某一段时间内&…...

mysql的登录与退出

mysql是c/s架构&#xff0c;意味着同时要有客户端和服务端 1 找到客户端。mysql.exe的安装目录 打开命令行 2 输入对应的服务器的ip&#xff0c;如果是本地&#xff0c;就是Localhost&#xff0c;如果是远程服务器&#xff0c;那就输入对应ip/域名。并且指定mysql监听的端口 …...

SOLIDWORKS工程图转DWG图层映射技巧

DWG格式的图纸在工程制图中有着非常重要的地位&#xff0c;工程实践中常常就需要将SOLIDWORKS工程图进行转换。对于两者之间数据衔接的妥善处理&#xff0c;是提升工作效率的有效手段。基于此目的&#xff0c;本次我们将介绍数据衔接的一个有效解决方案&#xff1a;图层数据的映…...

PMAC与Modbus主站进行Modbus Tcp通讯

PMAC与Modbus主站进行Modbus Tcp通讯 创建modbus通讯参数 在项目的PMAC Script Language\Global Includes下创建一个名为00_Modbus_Para.pmh的pmh文件。 Modbus[0].Config.ServerPort 0 Modbus[0].Config.ConnectTimeOut 6000 Modbus[0].Config.SendRecvTimeOut 0 Modbu…...

MyBatis分页插件PageHelper的使用及MyBatis的特殊符号---详细介绍

一&#xff0c;分页的概念 分页是一种将大量数据或内容分割成多个页面以便逐页显示的方式。在分页中&#xff0c;数据被分割成一定数量的页&#xff0c;每页显示一部分数据或内容&#xff0c;用户可以通过翻页或跳分页是一种将大量数据或内容分割成多个页面以便逐页显示的方式。…...

Qt(C++)计算一段程序执行经过的时间

一、前言 在许多应用程序和系统中,需要对经过的时间进行计算和记录。例如 可能想要测量某个操作的执行时间,或者记录一个过程中经过的时间以进行性能分析。在这些场景下,准确地计时是非常重要的。 Qt提供了一个功能强大的计时器类QElapsedTimer,可以方便地记录经过的时间…...

UnionTech OS(统信桌面操作系统)安装 g++ 和 cmake

文章目录 前言一、debian 10简介二、安装 g三、安装cmake参考资料 前言 统信桌面操作系统支持x86、龙芯、申威、鲲鹏、飞腾、兆芯等国产CPU平台&#xff0c;基于debian 10.x 的稳定版本&#xff0c;长期维护的统一内核版本(4.19)。 一、debian 10简介 Debian 10 是一款广泛使…...

php_webshell免杀--从0改造你的AntSword

0x00 前言&#xff1a; 为什么会有改造蚁剑的想法&#xff0c;之前看到有做冰蝎的流量加密&#xff0c;来看到绕过waf&#xff0c;改造一些弱特征&#xff0c;通过流量转换&#xff0c;跳过密钥交互。 但是&#xff0c;冰蝎需要反编译去改造源码&#xff0c;再进行修复bug&am…...

RocketMQ mqadmin java springboot python 调用笔记

命令 mqadmin命令列表 yeqiangyeqiang-MS-7B23:/opt/rocketmq-all-5.1.3-bin-release$ sh bin/mqadmin The most commonly used mqadmin commands are:updateTopic Update or create topicdeleteTopic Delete topic from broker and NameServer.…...

Java aspose 将HTML导出成Excel文件

1.需求 有一批表格的html文件&#xff0c;需要将这些表格导出成excel文件 2.代码 使用第三方库 aspose ByteArrayInputStream htmlIs new ByteArrayInputStream(htmlBuilder.toString().getBytes()); // 将html字符串构建成输入流 LoadOptions lo new LoadOptions(LoadFo…...

原生微信小程序 动态(横向,纵向)公告(广告)栏

先看一下动态效果 Y轴滚动公告的原理是swiper组件在页面中的Y轴滚动&#xff0c;属性vertical&#xff0c;其余属性也设置一下autoplay circular interval"3000" X轴滚动的原理是&#xff0c;利用动画效果&#xff0c;将内容从右往左过渡过去 wxml&#xff1a; &l…...

UE5 学习系列(二)用户操作界面及介绍

这篇博客是 UE5 学习系列博客的第二篇&#xff0c;在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下&#xff1a; 【Note】&#xff1a;如果你已经完成安装等操作&#xff0c;可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作&#xff0c;重…...

Cursor实现用excel数据填充word模版的方法

cursor主页&#xff1a;https://www.cursor.com/ 任务目标&#xff1a;把excel格式的数据里的单元格&#xff0c;按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例&#xff0c;…...

边缘计算医疗风险自查APP开发方案

核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...

Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)

概述 在 Swift 开发语言中&#xff0c;各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过&#xff0c;在涉及到多个子类派生于基类进行多态模拟的场景下&#xff0c;…...

visual studio 2022更改主题为深色

visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中&#xff0c;选择 环境 -> 常规 &#xff0c;将其中的颜色主题改成深色 点击确定&#xff0c;更改完成...

工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配

AI3D视觉的工业赋能者 迁移科技成立于2017年&#xff0c;作为行业领先的3D工业相机及视觉系统供应商&#xff0c;累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成&#xff0c;通过稳定、易用、高回报的AI3D视觉系统&#xff0c;为汽车、新能源、金属制造等行…...

【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具

第2章 虚拟机性能监控&#xff0c;故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令&#xff1a;jps [options] [hostid] 功能&#xff1a;本地虚拟机进程显示进程ID&#xff08;与ps相同&#xff09;&#xff0c;可同时显示主类&#x…...

图表类系列各种样式PPT模版分享

图标图表系列PPT模版&#xff0c;柱状图PPT模版&#xff0c;线状图PPT模版&#xff0c;折线图PPT模版&#xff0c;饼状图PPT模版&#xff0c;雷达图PPT模版&#xff0c;树状图PPT模版 图表类系列各种样式PPT模版分享&#xff1a;图表系列PPT模板https://pan.quark.cn/s/20d40aa…...

HashMap中的put方法执行流程(流程图)

1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中&#xff0c;其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下&#xff1a; 初始判断与哈希计算&#xff1a; 首先&#xff0c;putVal 方法会检查当前的 table&#xff08;也就…...

Python Einops库:深度学习中的张量操作革命

Einops&#xff08;爱因斯坦操作库&#xff09;就像给张量操作戴上了一副"语义眼镜"——让你用人类能理解的方式告诉计算机如何操作多维数组。这个基于爱因斯坦求和约定的库&#xff0c;用类似自然语言的表达式替代了晦涩的API调用&#xff0c;彻底改变了深度学习工程…...