当前位置: 首页 > 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…...

[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?

&#x1f9e0; 智能合约中的数据是如何在区块链中保持一致的&#xff1f; 为什么所有区块链节点都能得出相同结果&#xff1f;合约调用这么复杂&#xff0c;状态真能保持一致吗&#xff1f;本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里&#xf…...

铭豹扩展坞 USB转网口 突然无法识别解决方法

当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...

测试微信模版消息推送

进入“开发接口管理”--“公众平台测试账号”&#xff0c;无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息&#xff1a; 关注测试号&#xff1a;扫二维码关注测试号。 发送模版消息&#xff1a; import requests da…...

大数据零基础学习day1之环境准备和大数据初步理解

学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 &#xff08;1&#xff09;设置网关 打开VMware虚拟机&#xff0c;点击编辑…...

NFT模式:数字资产确权与链游经济系统构建

NFT模式&#xff1a;数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新&#xff1a;构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议&#xff1a;基于LayerZero协议实现以太坊、Solana等公链资产互通&#xff0c;通过零知…...

MySQL用户和授权

开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务&#xff1a; test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...

安宝特方案丨船舶智造的“AR+AI+作业标准化管理解决方案”(装配)

船舶制造装配管理现状&#xff1a;装配工作依赖人工经验&#xff0c;装配工人凭借长期实践积累的操作技巧完成零部件组装。企业通常制定了装配作业指导书&#xff0c;但在实际执行中&#xff0c;工人对指导书的理解和遵循程度参差不齐。 船舶装配过程中的挑战与需求 挑战 (1…...

VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP

编辑-虚拟网络编辑器-更改设置 选择桥接模式&#xff0c;然后找到相应的网卡&#xff08;可以查看自己本机的网络连接&#xff09; windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置&#xff0c;选择刚才配置的桥接模式 静态ip设置&#xff1a; 我用的ubuntu24桌…...

保姆级【快数学会Android端“动画“】+ 实现补间动画和逐帧动画!!!

目录 补间动画 1.创建资源文件夹 2.设置文件夹类型 3.创建.xml文件 4.样式设计 5.动画设置 6.动画的实现 内容拓展 7.在原基础上继续添加.xml文件 8.xml代码编写 (1)rotate_anim (2)scale_anim (3)translate_anim 9.MainActivity.java代码汇总 10.效果展示 逐帧…...

Sklearn 机器学习 缺失值处理 获取填充失值的统计值

💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 使用 Scikit-learn 处理缺失值并提取填充统计信息的完整指南 在机器学习项目中,数据清…...