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

力扣1038. 从二叉搜索树到更大和树(java,树的中序遍历解法)

Problem: 1038. 从二叉搜索树到更大和树

文章目录

  • 题目描述
  • 思路
  • 解题方法
  • 复杂度
  • Code

题目描述

给定一个二叉搜索树 root (BST),请将它的每个节点的值替换成树中大于或者等于该节点值的所有节点值之和。

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

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

示例 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]

提示:

树中的节点数在 [1, 100] 范围内。
0 <= Node.val <= 100
树中的所有值均 不重复 。

思路

我们易得到对于一个二叉搜索树,若我们按右-根-左的顺序递归中序遍历可以的得到一个递减的节点值序列,我们再利用一个变量在的过程中将当前的节点值加到变量中再将当前节点值修改为当前的变量值。

解题方法

1.记录一个成员变量sum用于记录中序遍历序列的累加值
2.按右-根-左的顺序递归中序遍历,递归结束条件为root == null
3.在归的过程中让sum加上当前节点值,再让sum赋值给当前节点值

复杂度

  • 时间复杂度:

O ( n ) O(n) O(n)

  • 空间复杂度:

O ( n ) O(n) O(n)

Code


/*** 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 {//Time Complexity: O(n)//Space Complexity: O(n)int sum = 0;public TreeNode bstToGst(TreeNode root) {resInorder(root);return root;}private void resInorder(TreeNode root) {if (root == null) return;resInorder(root.right);sum += root.val;root.val = sum;resInorder(root.left);}
}

相关文章:

力扣1038. 从二叉搜索树到更大和树(java,树的中序遍历解法)

Problem: 1038. 从二叉搜索树到更大和树 文章目录 题目描述思路解题方法复杂度Code 题目描述 给定一个二叉搜索树 root (BST)&#xff0c;请将它的每个节点的值替换成树中大于或者等于该节点值的所有节点值之和。 提醒一下&#xff0c; 二叉搜索树 满足下列约束条件&#xff…...

使用正则表达式来判断一个字符串只是否包含数字

使用正则表达式来判断一个字符串只是否包含数字 1、第一种 import java.util.regex.Pattern;public class Main {public static void main(String[] args) {String inputString "12345";if (containsOnlyDigits(inputString)) {System.out.println("字符串只…...

C#Wpf关于日志的相关功能扩展

目录 一、日志Sink(接收器) 二、Trace追踪实现日志 三、日志滚动 一、日志Sink(接收器) 安装NuGet包&#xff1a;Serilog Sink有很多种&#xff0c;这里介绍两种&#xff1a; Console接收器&#xff08;安装Serilog.Sinks.Console&#xff09;; File接收器&#xff08;安装…...

亚马逊云科技AI创新应用下的托管在AWS上的数据可视化工具—— Amazon QuickSight

目录 Amazon QuickSight简介 Amazon QuickSight的独特之处 Amazon QuickSight注册 Amazon QuickSight使用 Redshift和Amazon QuickSightt平台构建数据可视化应用程序 构建数据仓库 数据可视化 Amazon QuickSight简介 亚马逊QuickSight是一项可用于交付的云级商业智能 (BI…...

MySQL安全性:用户认证、防范SQL注入和SSL/TLS配置详解

MySQL作为广泛使用的关系型数据库管理系统&#xff0c;安全性至关重要。在本篇技术博客中&#xff0c;我们将深入探讨MySQL的用户认证方式、防范SQL注入攻击的方法以及SSL/TLS加密的配置。 1. MySQL用户认证方式 MySQL支持多种用户认证方式&#xff0c;其中两种常见方式是cac…...

EMG肌肉信号处理合集 (一)

本文归纳了常见的肌肉信号预处理流程&#xff0c;方便EMG信号的后续分析。使用pyemgpipeline库 来进行信号的处理。文中使用了 UC Irvine 数据库的下肢数据。 目录 1 使用wrappers 定义数据类&#xff0c;来进行后续的操作 2 肌电信号DC偏置去除 3 带通滤波器处理 4 对肌电…...

学自动化测试?我劝你还是算了吧。。。

本人7年测试经验&#xff0c;在学测试之前对电脑的认知也就只限于上个网&#xff0c;玩个办公软件。这里不能跑题&#xff0c;我为啥说&#xff1a;自学软件测试&#xff0c;一般人我还是劝你算了吧&#xff1f;因为我就是那个一般人&#xff01; 软件测试基础真的很简单&…...

第一百七十八回 介绍一个三方包组件:SlideSwitch

文章目录 1. 概念介绍2. 使用方法3. 代码与效果3.1 示例代码3.2 运行效果 4. 内容总结 我们在上一章回中介绍了"如何创建垂直方向的Switch"相关的内容&#xff0c;本章回中将 介绍SlideSwitch组件.闲话休提&#xff0c;让我们一起Talk Flutter吧。 1. 概念介绍 我们…...

Windows任务管理器内存性能界面各个参数含义

任务管理器的内存性能界面提供了一些关键参数&#xff0c;这些参数可以帮助你了解系统中内存的使用情况。以下是一些常见的参数及其含义&#xff1a; 已提交&#xff08;Committed&#xff09;&#xff1a; 表示已分配的物理内存和虚拟内存的总和。已提交的内存包括当前正在使…...

深度学习人脸表情识别算法 - opencv python 机器视觉 计算机竞赛

文章目录 0 前言1 技术介绍1.1 技术概括1.2 目前表情识别实现技术 2 实现效果3 深度学习表情识别实现过程3.1 网络架构3.2 数据3.3 实现流程3.4 部分实现代码 4 最后 0 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 &#x1f6a9; 深度学习人脸表情识别系…...

全职RISC-V芯片D1开发板使用adb串口COM连接设备和文件上传下载

将两个USB端口都连接到工作电脑 推荐使用ADB工具访问开发板&#xff0c;下载连接如下&#xff1a; Windows版本&#xff1a;https://dl.google.com/android/repository/platform-tools-latest-windows.zip Mac版本&#xff1a;https://dl.google.com/android/repository/pla…...

STM32笔记---RTC

目录 一、RTC简介 二、主要特性 三、功能描述 3.1 读RTC寄存器 3.2 配置RTC寄存器 四、BKP简介 五、RTC_Init() 1. 函数BKP_ReadBackupRegister 2.RCC_LSEConfig设置外部低速晶振&#xff08;LSE&#xff09; 3.RTC基本结构 5.RTC_Init()实现 6.time.h 一、R…...

C语言之strstr函数的使用和模拟实现

C语言之strstr函数的模拟实现 文章目录 C语言之strstr函数的模拟实现1. strstr函数的介绍2. strstr函数的使用3. strstr的模拟实现3.1 实现思路3.2 实现代码 1. strstr函数的介绍 函数声明如下&#xff1a; char * strstr ( const char * str1, const char * str2 ); strs…...

【间歇振荡器2片555时基仿真】2022-9-24

缘由multisim出现这个应该怎么解决吖&#xff0c;急需解决-嵌入式-CSDN问答 输出一定要有电阻分压才能前后连接控制否则一定报错。...

MySQL与PostgreSQL 的一些SQL

MySQL 1、MYSQL输出重定向 将SQL内容输出到文件 nohup mysql -h127.0.0.1 -uroot -ppassword -Ne "sql语句;" > /home/mysql/data/xxxxx.txt &2、时间格式转换 时间转换&#xff0c;转10位时间戳 select UNIX_TIMESTAMP(2021-02-27 00:00:00)SELECT …...

Spring 七大组件

文章目录 Spring 七大组件 Spring 七大组件 核心容器(Spring core) 核心容器提供Spring框架的基本功能。Spring以bean的方式组织和管理Java应用中的各个组件及其关系。Spring使用BeanFactory来产生和管理Bean&#xff0c;它是工厂模式的实现。BeanFactory使用控制反转(IOC)模式…...

【UGUI】实现跑酷游戏分数血量显示在UI中

//1.实现让玩家的金币分数显示在UI文本中 2.让血量和滑动条关联起来 这一节课主要学会获取组件并改变属性&#xff0c;举一反三&#xff01; using System.Collections; using System.Collections.Generic; using UnityEngine; using UnityEngine.UI; using TMPro;//1.实现让玩…...

Vue和React对比

Vue和React都是流行的前端JavaScript框架&#xff0c;它们有很多相似点和不同点&#xff0c;以下是它们的优缺点。 相似点&#xff1a; 都使用了组件化的开发模式&#xff0c;使得应用程序更易于理解和维护。都支持虚拟DOM&#xff0c;提高了页面重绘性能。都支持模板化编程方…...

iPhone的实时照片不能直接查看,但有不少替代方法可以查看

​苹果在iPhone 6s和iPhone 6s Plus上推出了实时照片(livp)功能,该功能也出现在最新的iPhone中。正如你所知,实时照片功能是电影和静态图像的混合。也就是说,实时照片既不是照片也不是视频。 当你在iPhone上拍摄实时照片时,iOS会创建一个MOV文件和一个JPEG文件。 如果你…...

弹窗msvcp140_1.dll丢失的解决方法,超简单的方法分享

在计算机使用过程中&#xff0c;我们经常会遇到一些错误提示&#xff0c;其中最常见的就是缺少某个文件的错误。最近&#xff0c;我在使用某些软件时&#xff0c;遇到了一个名为“msvcp140_1.dll”的错误提示。这个错误通常出现在运行某些程序时&#xff0c;由于缺少了msvcp140…...

SkyWalking 10.2.0 SWCK 配置过程

SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外&#xff0c;K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案&#xff0c;全安装在K8S群集中。 具体可参…...

《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)

CSI-2 协议详细解析 (一&#xff09; 1. CSI-2层定义&#xff08;CSI-2 Layer Definitions&#xff09; 分层结构 &#xff1a;CSI-2协议分为6层&#xff1a; 物理层&#xff08;PHY Layer&#xff09; &#xff1a; 定义电气特性、时钟机制和传输介质&#xff08;导线&#…...

渲染学进阶内容——模型

最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...

【2025年】解决Burpsuite抓不到https包的问题

环境&#xff1a;windows11 burpsuite:2025.5 在抓取https网站时&#xff0c;burpsuite抓取不到https数据包&#xff0c;只显示&#xff1a; 解决该问题只需如下三个步骤&#xff1a; 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...

DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI

前一阵子在百度 AI 开发者大会上&#xff0c;看到基于小智 AI DIY 玩具的演示&#xff0c;感觉有点意思&#xff0c;想着自己也来试试。 如果只是想烧录现成的固件&#xff0c;乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外&#xff0c;还提供了基于网页版的 ESP LA…...

Spring Boot面试题精选汇总

&#x1f91f;致敬读者 &#x1f7e9;感谢阅读&#x1f7e6;笑口常开&#x1f7ea;生日快乐⬛早点睡觉 &#x1f4d8;博主相关 &#x1f7e7;博主信息&#x1f7e8;博客首页&#x1f7eb;专栏推荐&#x1f7e5;活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...

汇编常见指令

汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX&#xff08;不访问内存&#xff09;XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...

Java面试专项一-准备篇

一、企业简历筛选规则 一般企业的简历筛选流程&#xff1a;首先由HR先筛选一部分简历后&#xff0c;在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如&#xff1a;Boss直聘&#xff08;招聘方平台&#xff09; 直接按照条件进行筛选 例如&#xff1a…...

【MATLAB代码】基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),附源代码|订阅专栏后可直接查看

文章所述的代码实现了基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),针对传感器观测数据中存在的脉冲型异常噪声问题,通过非线性加权机制提升滤波器的抗干扰能力。代码通过对比传统KF与MCC-KF在含异常值场景下的表现,验证了后者在状态估计鲁棒性方面的显著优…...

抽象类和接口(全)

一、抽象类 1.概念&#xff1a;如果⼀个类中没有包含⾜够的信息来描绘⼀个具体的对象&#xff0c;这样的类就是抽象类。 像是没有实际⼯作的⽅法,我们可以把它设计成⼀个抽象⽅法&#xff0c;包含抽象⽅法的类我们称为抽象类。 2.语法 在Java中&#xff0c;⼀个类如果被 abs…...