代码随想录【Day23】| 669. 修剪二叉搜索树、108. 将有序数组转换为二叉搜索树、538. 把二叉搜索树转换为累加树
669. 修剪二叉搜索树
题目链接
题目描述:
给定一个二叉搜索树,同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树,使得所有节点的值在[L, R]中 (R>=L) 。你可能需要改变树的根节点,所以结果应当返回修剪好的二叉搜索树的新的根节点。

难点:
思路:
主要操作和上一题BST中删除根节点的操作类似
但是要注意其他细节:
采用前序遍历,
-
需要更新根节点:当根节点(包括更新后的)落在
[low, high]区间外,要进行连续删除
1.1 如果左右子树均为空:直接返回null
1.2 如果左子树不为空,右子树为空:更新当前根节点为左孩子
1.3 如果左子树为空,右子树不为空:更新当前根节点为右孩子
1.4 如果左右子树均不为空:那就调整BST -
不需要更新根节点:递归遍历左、右子树
class Solution {public TreeNode trimBST(TreeNode root, int low, int high) {if (root == null) return null;while (root.val < low || root.val > high) { //删除根结点(包括更新后的根节点)if (root.left == null && root.right == null) return null;if (root.left == null && root.right != null) { //更新根节点root = root.right;continue;}if (root.right == null && root.left != null) { //更新根节点root = root.left;continue;}TreeNode tmp = root.right;while (tmp.left != null) {tmp = tmp.left;}tmp.left = root.left;root = root.right;}root.left = trimBST(root.left, low, high);root.right = trimBST(root.right, low, high);return root;}
}
以上是自己敲的
继续精简可以写成↓,哇咔咔,牛的!
//代码随想录参考代码
class Solution {public TreeNode trimBST(TreeNode root, int low, int high) {if (root == null) {return null;}if (root.val < low) {return trimBST(root.right, low, high);}if (root.val > high) {return trimBST(root.left, low, high);}// root在[low,high]范围内root.left = trimBST(root.left, low, high);root.right = trimBST(root.right, low, high);return root;}
}
时长:
20min
收获:
多情况分析
108. 将有序数组转换为二叉搜索树
题目链接
题目描述:
将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。
本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:

难点:
思路:
因为给定数组是有序的,采用二分法进行构造就可以保证BST是平衡的
//左闭右闭[left, right]
class Solution {public TreeNode sortedArrayToBST(int[] nums) {return buildBST(nums, 0, nums.length-1);}public TreeNode buildBST(int[] nums, int left, int right) {if (left > right) return null;int mid = (left+right)/2;TreeNode root = new TreeNode(nums[mid]);root.left = buildBST(nums, left, mid-1);root.right = buildBST(nums, mid+1, right);return root;}
}//左闭右开[left, right)
class Solution {public TreeNode sortedArrayToBST(int[] nums) {return buildBST(nums, 0, nums.length);}public TreeNode buildBST(int[] nums, int left, int right) {if (left >= right) return null;int mid = (left+right)/2;TreeNode root = new TreeNode(nums[mid]);root.left = buildBST(nums, left, mid);root.right = buildBST(nums, mid+1, right);return root;}
}
时长:
6min
收获:
二分法复习
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 之间。
树中的所有值 互不相同 。
给定的树为二叉搜索树。
难点:
思路:
根据题目要求以及观察示例
应该采用“右中左”的遍历顺序来构造
class Solution {int curSum;public TreeNode convertBST(TreeNode root) {if (root == null) return null;root.right = convertBST(root.right);curSum += root.val;root.val = curSum;root.left = convertBST(root.left);return root;}
}
时长:
8min
收获:
。。。
相关文章:
代码随想录【Day23】| 669. 修剪二叉搜索树、108. 将有序数组转换为二叉搜索树、538. 把二叉搜索树转换为累加树
669. 修剪二叉搜索树 题目链接 题目描述: 给定一个二叉搜索树,同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树,使得所有节点的值在[L, R]中 (R>L) 。你可能需要改变树的根节点,所以结果应当返回修剪好的二叉搜索树的新…...
Wsl2 ubuntu 配置git 阿里云codeup
目录 创建一个跟你windows git使用相同的用户名,特别重要 配置git 用户名和邮箱 配置阿里云codeup 拉取仓库提示文件权限问题 给用户目录权限 配置项目文件别名 key_load_public: invalid format 怎么办? WSL ubuntu sshd: no hostkeys available -- exiting…...
展会邀约 | 昂视与您相约BTF第12届上海锂电展
BTF第12届上海国际新能源锂电展将于3月7日在上海新国际博览中心举办。此次展会以“锂想动力,共创未来”为主题,汇聚行业内一众翘楚企业与专业观众,为各位展商以及观众提供专业的锂电交流平台,了解与碰撞新产品、新技术与解决方案&…...
RK3568平台开发系列讲解(驱动基础篇)中断子系统框架
🚀返回专栏总目录 文章目录 一、中断硬件的组成二、软件框架三、中断常见概念沉淀、分享、成长,让自己和他人都能有所收获!😄 📢中断是指 CPU 正常运行期间,由于内外部事件或程序预先安排的事件,引起的 CPU 暂时停止正在运行的程序, 转而为该内部或外部预先安排的事…...
消费复苏迎“春”暖,服装行业如何开启“狂飙”模式?
2023年开年前2个月,全国多地消费市场的“热度”一直在持续上涨,商场、餐馆、娱乐场所等消费市场人气旺盛,消费复苏的“暖”意十足,一幕幕“忙”起来、“热”起来的场景,让各行各业的商家都对未来充满了期待与信心。在消…...
Springboot 整合Flowable工作流框架搭建
我们在开发自动化办公软件时经常会遇到各种审批流程功能,这个使用就需要使用到工作流引擎。目前主流的工作流引擎有Activiti、Flowable、camunda,其中Flowable是在Activiti的基础上开发出来的,基于BPMN2.0协议,它包括 BPMN&#x…...
ASE0510SH-ASEMI的MOS管ASE0510SH
编辑-Z ASE0510SH在SOT-89封装里的静态漏极源导通电阻(RDS(ON))为140mΩ,是一款N沟道中低压MOS管。ASE0510SH的最大脉冲正向电流ISM为15A,零栅极电压漏极电流(IDSS)为1uA,其工作时耐温度范围为-55~150摄氏度。ASE0510…...
Golang学习Day2
Go语言中的函数go语言中函数特性go语言有三种函数:普通函数、匿名函数(没有名称的函数)方法(定义在struct上的函数)。receivergo语言中不运算函数重载(overload),也就是说不允许函数…...
Android 中malloc_debug 原理详解
版本基于:Android R 0. 前言 最近上项目中遇到一个native 可能内存泄漏的问题,曾考虑使用HWASAN,但这个工具是针对整个系统,运行代价还是很高的。而笔者遇到的问题大致有所方向,能指定到某一个进程,针对单…...
D. Triangle Coloring【组合数学,乘法逆元】
链接 分析 题目要求我们去求出最优的染色的方法数。首先什么时候是最优的,这里只有两种颜色,不可能取到三条边,即蓝色为B,红色为R,有BBB,RRR,BBR,RRB四种组合,显然最多的就是取两条边,我们想取到…...
【读论文】AttentionFGAN
【读论文】AttentionFGAN介绍网络架构提取红外图像目标信息的网络辨别器损失函数生成器损失函数辨别器损失函数总结参考论文: https://ieeexplore.ieee.org/document/9103116/如有侵权请联系博主介绍 好久没有读过使用GAN来实现图像融合的论文了,正好看…...
ClickHouse 配置文件使用说明
本文主要介绍 ClickHouse 的配置文件。在 ClickHouse 中配置主要分为两类,一类是负责 server 端配置的,另一类是负责用户端配置的。负责 server 端配置的一般会放在 config.xml 文件中,负责用户端配置的一般会放在 users.xml 文件中。当然如果…...
如果不是互联网人,谁会找到这些神器?
一、上线啦 你肯定该问了,这个是什么鬼东西。它本来是一个创建自己网站的网站。 现在使用它可以创建自己的小程序,又不是有点小厉害了。 而且功能强大,还支持微信支付,分销,优惠券,营销等多种功能。 还有多…...
Neo4j优化
使用参数 查询参数 :params设置参数 :param actorName: Tom Hanks参数的冒号后要用空格使用参数用 $ MATCH (p:Person)-[:ACTED_IN]->(m:Movie) WHERE p.name $actorName RETURN m.released AS releaseDate,m.title AS title ORDER BY m.released DESC多个参数 MATCH (p:Pe…...
CF1692G 2^Sort 题解
CF1692G 2^Sort 题解题目链接字面描述题面翻译题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1提示思路代码实现题目 链接 https://www.luogu.com.cn/problem/CF1692G 字面描述 题面翻译 给你一个长度为 n(∑n<2⋅105)n \ (\sum n < 2\cdot 10^5)n (∑n<…...
关于物理像素,逻辑像素,像素比
关于物理像素、逻辑像素(css像素)、分辨率、像素比的超详细讲解 在日常生活中,有这样一个问题。同样的图片为什么在不同的设备上显示的大小是不一样的。🤒带着这个问题来说明一下。 一、物理像素 设备刚生产出来就已经固定了&a…...
JavaSE基础部分总结
JavaSe基础部分 文章目录JavaSe基础部分1.命名规范2.基本的数据类型3.方法3.1方法的基本格式3.2 方法的分类3.3 方法的注释4.数组4.1 数组的命名格式4.2 数组中存在的址交换的操作4.3数组Arrays常用的方法1. Arrays.asList(数组作为参数或者数据作为参数):2.Arrays.…...
C++基础知识
目录类和对象C static_cast、dynamic_cast、const_cast和reinterpret_cast1、为什么要引入这四种类型转化?2、应用场景。C/C类型转换的本质struct和class的区别为什么会诞生面向对象的编程思想析构函数的执行时机初始化 const 成员变量C const对象(常对象…...
2023/2/24 图数据库Neo4j的理解与应用
1 什么是图数据库(graph database) 十大应用案例:https://go.neo4j.com/rs/710-RRC-335/images/Neo4j-Top-Use-Cases-ZH.pdf “大数据”每年都在增长,但如今的企业领导者不仅需要管理更大规模的数据,还迫切需要从现有…...
适合视力障碍者的Linux
导读有哪些最适合视障用户的 Linux 发行版?让我们一起来看看。 如果有人视力障碍或失明,他们可能会依赖声音提示或其他交互方式(如盲文)来阅读和交流。 他们怎样才能使用 Linux 发行版? 嗯,一般来说&…...
Java 8 Stream API 入门到实践详解
一、告别 for 循环! 传统痛点: Java 8 之前,集合操作离不开冗长的 for 循环和匿名类。例如,过滤列表中的偶数: List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...
Opencv中的addweighted函数
一.addweighted函数作用 addweighted()是OpenCV库中用于图像处理的函数,主要功能是将两个输入图像(尺寸和类型相同)按照指定的权重进行加权叠加(图像融合),并添加一个标量值&#x…...
学校招生小程序源码介绍
基于ThinkPHPFastAdminUniApp开发的学校招生小程序源码,专为学校招生场景量身打造,功能实用且操作便捷。 从技术架构来看,ThinkPHP提供稳定可靠的后台服务,FastAdmin加速开发流程,UniApp则保障小程序在多端有良好的兼…...
Keil 中设置 STM32 Flash 和 RAM 地址详解
文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...
[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...
leetcodeSQL解题:3564. 季节性销售分析
leetcodeSQL解题:3564. 季节性销售分析 题目: 表:sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...
EtherNet/IP转DeviceNet协议网关详解
一,设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络,本网关连接到EtherNet/IP总线中做为从站使用,连接到DeviceNet总线中做为从站使用。 在自动…...
c#开发AI模型对话
AI模型 前面已经介绍了一般AI模型本地部署,直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型,但是目前国内可能使用不多,至少实践例子很少看见。开发训练模型就不介绍了&am…...
全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比
目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec? IPsec VPN 5.1 IPsec传输模式(Transport Mode) 5.2 IPsec隧道模式(Tunne…...
回溯算法学习
一、电话号码的字母组合 import java.util.ArrayList; import java.util.List;import javax.management.loading.PrivateClassLoader;public class letterCombinations {private static final String[] KEYPAD {"", //0"", //1"abc", //2"…...
