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

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

题目

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

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

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

示例 1:

输入:[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]

提示:

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

解答

源代码

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {    private int sum;public TreeNode convertBST(TreeNode root) {if (root != null) {convertBST(root.right);sum += root.val;root.val = sum;convertBST(root.left);}return root;}
}

总结

反序中序遍历。

一开始觉得每次都要把整个二叉树遍历一遍找到比当前节点大的节点,后来发现是二叉搜索树,右>中>左,所以从最大的节点开始逐渐往最小的节点遍历,也就是中序遍历反过来。

相关文章:

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

题目 给出二叉 搜索 树的根节点,该树的节点值各不相同,请你将其转换为累加树(Greater Sum Tree),使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。 提醒一下,二叉搜索树满足下列约束条件…...

linux 安装 kibana

首先下载 kibana https://www.elastic.co/cn/downloads/kibana 然后上传到linux /usr/local 目录下解压安装 修改config/kibana.yml 配置文件,将elasticsearch.hosts 然后再nginx 中做一个端口映射,实现在浏览器中输入后xxxx:5602 nginx 可以将请求转发…...

STM32入门——IIC通讯

江科大STM32学习记录 I2C通信 I2C(Inter IC Bus)是由Philips公司开发的一种通用数据总线两根通信线:SCL(Serial Clock)、SDA(Serial Data)同步,半双工带数据应答支持总线挂载多设备…...

DTC 19服务学习2

紧跟上篇 0x04 reportDTCSnapshotRecordByDTCNumber 通过DTC和快照序列来获取DTC快照记录。 适用以下假设: — 服务器支持存储给定 DTC 的两个 DTCSnapshot 记录的能力。 — 此示例假定是上一个示例的延续。 — 假设服务器请求服务器存储的 DTC 编号 123456 的两个…...

【腾讯云 TDSQL-C Serverless 产品体验】基于腾讯云轻量服务器以及 TDSQL-C 搭建 LNMP WordPress 博客系统

文章目录 一、前言二、数据库发展与云原生数据库2.1 数据库发展简介2.2 云原生数据库简介2.2.1 云数据库与云原生数据库区别 三、腾讯云 TDSQL-C 数据库3.1 什么是腾讯云 TDSQL-C 数据库3.2 为什么推出 TDSQL-C 数据库?传统 MySQL 架构存在较多痛点3.2.1 传统 MySQL…...

【vue3】对axios进行封装,方便更改路由并且可以改成局域网ip访问(附代码)

对axios封装是在main.js里面进行封装,因为main.js是一个vue项目的入口 步骤: 在1处创建一个axios实例为http,baseURL是基础地址(根据自己的需求写),写了这个在vue界面调用后端接口时只用在post请求处写路由…...

Java IO流(三)线程模型

传统阻塞I/O模式 其中黄色框表示对象,蓝色框表示线程,白色框表示API方法 特点 采用阻塞IO模式获取输入数据每个连接都需要独立的线程完成数据的输入,业务处理和处理结果数据返回 潜在问题 并发数很大时,需要对应每个连接请求创建一个线程,所以占用资源很大连接创建后,若当前…...

string(模拟实现与深拷贝)

目录 深拷贝与浅拷贝 浅拷贝: 深拷贝 写时拷贝(了解) 模拟实现 准备 完整代码 深拷贝与浅拷贝 浅拷贝: 也称位拷贝,编译器只是将对象中的值拷贝过来。如果对象中管理资源,最后就会导致多个对象共享同一份资源,当一…...

5.Vue_Element

文章目录 1 Ajax1.1 Ajax介绍1.1.1 Ajax概述1.1.2 Ajax作用1.1.3 同步异步 1.2 Axios1.2.1 Axios的基本使用1.2.2 Axios请求方法的别名 2 前端工程化2.1 前端工程化特点2.2 Vue项目开发流程 3 Vue组件库Element3.1 Element介绍 1 Ajax 1.1 Ajax介绍 1.1.1 Ajax概述 Ajax: 全…...

链路追踪jaeger

这里的链路指的是客户端向服务发起一个请求,该请求所经过的路线,也可以说是该请求经过的流量 例如: 客户端发起一个下订单的请求其流量过程: request—>service—>order-web—>order_srv—>mysql—>order_srv—&…...

神经网络基础-神经网络补充概念-42-梯度检验

概念 梯度检验(Gradient Checking)是一种验证数值计算梯度与解析计算梯度之间是否一致的技术,通常用于确保实现的反向传播算法正确性。在深度学习中,通过梯度检验可以帮助验证你的神经网络模型是否正确地计算了梯度,从…...

<kernel>kernel 6.4 USB-之-hub_port_connect()分析

<kernel>kernel 6.4 USB-之-hub_port_connect()分析 kernel 6.4 USB系列文章如下: <kernel>kernel 6.4 USB-之-hub_event()分析 <kernel>kernel 6.4 USB-之-port_event()分析 <kern…...

linux驱动学习3-外部中断

在做中断试验时,发现中断驱动总是insmod失败,之后定位到 gpio_request 失败,之后是想到使用的野火做好的系统,在uEnv.txt中会加载大量设备树插件,将key相关的设备树插件屏蔽即可。 linux中断API函数 中断号 每个中断…...

vue中的canvas插件

vue中canvas插件有vue-konva、vue-fabricjs、vue-canvas-effect、vue-chartjs和vue-threejs等。详细介绍:1、vue-konva是一个用于在Vue.js中使用Konva.js的插件,Konva.js是一个功能强大的HTML5 2D 渲染引擎,可以用于创建交互式的Canvas应用程…...

分享图片 | 快速浏览网页资源,批量保存、一键分享图片

前言 小伙伴学习吉他,有时需要在互联网搜索曲谱资源,而多数曲谱均为图片,并且为多页,在电脑上显示练习很不方便,需要停下来点击鼠标进行翻页,影响练习的连贯性。 为了解决上述问题,通常把图片…...

Programming abstractions in C阅读笔记:p123-p126

《Programming Abstractions In C》学习第50天,p123-p126,总结如下: 一、技术总结 1.notaion 这也是一个在计算机相关书籍中出现的词,但有时却不是那么好理解,因为它可以指代很多对象,这里做一个记录。示…...

自然语言处理从入门到应用——LangChain:链(Chains)-[通用功能:LLMChain、RouterChain和SequentialChain]

分类目录:《自然语言处理从入门到应用》总目录 LLMChain LLMChain是查询LLM对象最流行的方式之一。它使用提供的输入键值(如果有的话,还包括内存键值)格式化提示模板,将格式化的字符串传递给LLM,并返回LLM…...

ElasticSearch-安装部署全过程

本文已收录于专栏 《中间件合集》 目录 概念说明什么是ElasticSearch什么是Kibana什么是RESTful API 提供服务安装过程安装ElasticSearch1.下载ElasticSearch 安装包2.解压安装包3.进入解压之后的文件夹4.创建一个data文件夹用来存储数据5.进入config文件夹编辑elasticsearch.y…...

mathematica报错:Tag Plus is \ Protected

在使用化简函数Simplify的时候使用了规则的语法,但是规则可能没有使用等号。 例如 Simplify[(1 - c^2)/d^2, c^2 d^2 1]等号被认为是赋值符号,要修改为两个等号: Simplify[(1 - c^2)/d^2, c^2 d^2 1]这样就不会报错了。...

Python Django 模型概述与应用

今天来为大家介绍 Django 框架的模型部分,模型是真实数据的简单明确的描述,它包含了储存的数据所必要的字段和行为,Django 遵循 DRY Principle 。它的目标是你只需要定义数据模型,然后其它的杂七杂八代码你都不用关心,…...

接口测试中缓存处理策略

在接口测试中,缓存处理策略是一个关键环节,直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性,避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明: 一、缓存处理的核…...

从零实现富文本编辑器#5-编辑器选区模型的状态结构表达

先前我们总结了浏览器选区模型的交互策略,并且实现了基本的选区操作,还调研了自绘选区的实现。那么相对的,我们还需要设计编辑器的选区表达,也可以称为模型选区。编辑器中应用变更时的操作范围,就是以模型选区为基准来…...

CMake基础:构建流程详解

目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...

定时器任务——若依源码分析

分析util包下面的工具类schedule utils: ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类,封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz,先构建任务的 JobD…...

linux arm系统烧录

1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 (忘了有没有这步了 估计有) 刷机程序 和 镜像 就不提供了。要刷的时…...

HTML前端开发:JavaScript 常用事件详解

作为前端开发的核心,JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例: 1. onclick - 点击事件 当元素被单击时触发(左键点击) button.onclick function() {alert("按钮被点击了!&…...

SpringTask-03.入门案例

一.入门案例 启动类: package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...

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

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

Hive 存储格式深度解析:从 TextFile 到 ORC,如何选对数据存储方案?

在大数据处理领域,Hive 作为 Hadoop 生态中重要的数据仓库工具,其存储格式的选择直接影响数据存储成本、查询效率和计算资源消耗。面对 TextFile、SequenceFile、Parquet、RCFile、ORC 等多种存储格式,很多开发者常常陷入选择困境。本文将从底…...

【Java学习笔记】BigInteger 和 BigDecimal 类

BigInteger 和 BigDecimal 类 二者共有的常见方法 方法功能add加subtract减multiply乘divide除 注意点:传参类型必须是类对象 一、BigInteger 1. 作用:适合保存比较大的整型数 2. 使用说明 创建BigInteger对象 传入字符串 3. 代码示例 import j…...