【代码随想录训练营】【Day23】第六章|二叉树|669. 修剪二叉搜索树 |108.将有序数组转换为二叉搜索树|538.把二叉搜索树转换为累加树
修剪二叉搜索树
题目详细:LeetCode.669
做这道题之前建议先看视频讲解,没有想象中那么复杂:代码随想录—修剪二叉搜索树
由题可知,需要删除节点值不在区间内的节点,所以可以得到三种情况:
- 情况一:root.val < low
- 情况二:root.val > high
- 情况三:low < root.val < high
- 当节点满足情况一和情况二的条件时,删除该节点
但被删除节点的子树可能存在值在区间内的节点,利用二叉搜索树的特点可得:
- 情况一:root.val < low,root左子树上的节点值都比root.val小,右子树上的节点值都比root.val大,所以满足区间的节点只会在右子树上出现,递归修剪其右子树并返回新的子节点
- 情况二:root.val > high,root左子树上的节点值都比root.val小,右子树上的节点值都比root.val大,所以满足区间的节点只会在左子树上出现,递归修剪其左子树并返回新的子节点
- 情况三:low < root.val < high,说明当前节点不需要被删除,递归修剪其左右子树,返回修剪好的二叉搜索树的新的根节点
Java解法(递归):
class Solution {public TreeNode trimBST(TreeNode root, int low, int high) {if(null == root) return null;// 根据二叉搜索树的特点可知if(root.val < low){// 删除节点的右子树中可能存在值在区间内的节点// 返回修剪好的右子树的新的子节点return trimBST(root.right, low, high);}else if(root.val > high){// 删除节点的左子树中可能存在值在区间内的节点// 返回修剪好的左子树的新的子节点return trimBST(root.left, low, high);}// else if(root.val > low && root.val < high)// 递归修剪左右子树root.left = trimBST(root.left, low, high);root.right = trimBST(root.right, low, high);// 返回修剪好的二叉搜索树的新的根节点return root;}
}
将有序数组转换为二叉搜索树
题目详细:LeetCode.108
由题可知:
- 数组中的元素是有序排序的
- 转换的结果是为一棵高度平衡的二叉搜索树
要想使结果的二叉树高度平衡:
- 我们可以找中间值,根据中间值的下标将数组分为长度相近的两个子数组
- 利用数组有序的特点,其划分后的子数组依旧是有序的
- 左边的数值较小 < 中间值,右边的数值 > 中间值
- 所以我们可以将中间值作为根节点,左边的数值作为左子树的节点,右边的数值作为右子树的节点
- 采用递归,按照以上的逻辑不断划分数组和子树,当nums无法再分时,将空节点或节点返回给上一层接收,决定了节点的位置
- 最后返回转换完成的二叉搜索树的根节点
Java解法(递归):
class Solution {public TreeNode sortedArrayToBST(int[] nums) {if(nums.length == 0) return null;else if(nums.length == 1) return new TreeNode(nums[0]);// 计算中间值的位置,并划分构建左右子树的子数组int mid = nums.length / 2;int[] left_nums = Arrays.copyOfRange(nums, 0, mid);int[] right_nums = Arrays.copyOfRange(nums, mid+1, nums.length);// 最中间的数值作为树的根节点,递归构建左右子树TreeNode root = new TreeNode(nums[mid]);root.left = sortedArrayToBST(left_nums);root.right = sortedArrayToBST(right_nums);// 返回构建完成的二叉搜索树的根节点return root;}
}
把二叉搜索树转换为累加树
题目详细:LeetCode.538
做这道题之前建议先看视频讲解,没有想象中那么复杂:代码随想录—把二叉搜索树转换为累加树
Java解法(递归,双指针法):
class Solution {int pre = 0;public TreeNode convertBST(TreeNode root) {this.inorder(root);return root;}public void inorder(TreeNode cur){if(null == cur) return;inorder(cur.right);cur.val += this.pre;this.pre = cur.val;inorder(cur.left);}
}
相关文章:
【代码随想录训练营】【Day23】第六章|二叉树|669. 修剪二叉搜索树 |108.将有序数组转换为二叉搜索树|538.把二叉搜索树转换为累加树
修剪二叉搜索树 题目详细:LeetCode.669 做这道题之前建议先看视频讲解,没有想象中那么复杂:代码随想录—修剪二叉搜索树 由题可知,需要删除节点值不在区间内的节点,所以可以得到三种情况: 情况一&#…...
CV——day78 读论文:通过静态背景构建扩展低通道路边雷达的探测距离(目标是规避风险)
Extending the Detection Range for Low-Channel Roadside LiDAR by Static Background Construction 通过静态背景构建扩展低通道路边雷达的探测距离I. INTRODUCTIONII. RELATED WORKA. LiDAR-Based 3-D Vehicle and Road User DetectionB. LiDAR Data Background FilteringC.…...
【编程入门】应用市场(go语言版)
背景 前面已输出多个系列: 《十余种编程语言做个计算器》 《十余种编程语言写2048小游戏》 《17种编程语言10种排序算法》 《十余种编程语言写博客系统》 《十余种编程语言写云笔记》 《N种编程语言做个记事本》 目标 为编程初学者打造入门学习项目,使…...
Linux(openEuler)没有界面连接互联网方法
前言: 系统版本openEuleropenEuler-22.03-LTS-x86_64-dvd 我们在安装linux之后,一般都是无界面的情况。大部分情况都是需要自己安装界面的,如果路由器的情况下直接插上网络就好了。下面就开始介绍两种方法进行linxu网络的连接。 注意: 小编是使用的第一…...
第一天 软考中级--嵌入式系统设计师考试复习教程开始了
第一天 嵌入式系统设计师考试复习教程 第二天 软考中级--嵌入式系统设计师考试考试大纲解析 目录...
分享 10 个高频 Python 面试题
Python 很容易学会,但很难掌握。你可以在几天内了解它的基本语法,但是要能够用 Python 开发出足够好的商业软件,多年的实践是必须的。因为,无论你使用哪种编程语言,你都必须对其复杂的内部机制有足够的了解,…...
ThreadLocal原理、结构、源码解析
文章目录一、Thread简介1.什么是ThreadLocal2.为什么要是用ThreadLocal2.1Synchronized、Lock保证线程安全2.2ThreadLocal保证线程安全3.ThreadLocal和Synchronized的区别二、ThreadLocal原理1.Thread抽象内部结构2.ThreadLocal源码2.1Thread、ThreadLocal、ThreadLocalMap、En…...
分布式之PBFT算法
写在前面 在分布式之拜占庭问题 一文中我们分析了拜占庭问题,并一起看了支持拜占庭容错的口信消息性和签名消息性算法,但是这两种算法都有一个非常严重的问题,就是消息数量太多,通信的成本太大,消息数量复杂度为O(n ^…...
Linux 操作系统——查看/修改系统时区、时间、本地时间修改为UTC
文章目录1.背景描述2.知识储备3.解决步骤1. 查看当前时区2.修改设置Linux服务器时区3.复制相应的时区文件,替换系统时区文件;或者创建链接文件4. 查看和修改Linux的时间5. 硬件时间和系统时间的 相互同步1.背景描述 最近一个项目日期采用java8的LocalDa…...
CSS数据类型以及符号
css数据类型定义的是css属性中具有代表性的值,在规范的语法格式中,使用关键字外加一对 <和>表示,例如数值类型<number>、色值类型<color>等。 举个例子:background-image这个css属性语法结构如下: …...
LeetCode-54. 螺旋矩阵
题目来源 54. 螺旋矩阵 题目思路 while循环只遍历"环",不成环就不遍历了 四个边界 上边界 top : 0下边界 bottom : matrix.length - 1左边界 left : 0右边界 right : matrix[0].length - 1 矩阵不一定是方阵 top < bottom && left < r…...
【Python入门第十八天】Python For 循环
Python For 循环 for 循环用于迭代序列(即列表,元组,字典,集合或字符串)。 这与其他编程语言中的 for 关键字不太相似,而是更像其他面向对象编程语言中的迭代器方法。 通过使用 for 循环,我们…...
Qt图片定时滚动播放器
目录参考结构PicturePlay.promain.cpppictureplay.hpictureplay.cpppictureplay.ui效果源码参考 Qt图片浏览器 QT制作一个图片播放器 Qt中自适应的labelpixmap充满窗口后,无法缩小只能放大 可以显示jpg、jpeg、png、bmp。可以从电脑上拖动图到窗口并显示出来或者打开…...
李宏毅2023春季机器学习课程
目录2021&2022课程重磅须知我维护的其他项目更新日志课程地址课程资料直链课程作业直链其他优质课程2021&2022课程 CSDN Github 重磅须知 为方便所有网课资料与优质电子书籍的实时更新维护,创建一个在线实时网盘文件夹; 网盘获取方式&#…...
计算机操作系统知识点汇总
计算机操作系统选择填空题,300知识点,包含操作系统概论、处理机管理、内存管理、设备管理、文件管理等,为大学生期末创造奇迹提供无限可能 1、填空题 1、操作系统是对计算机资源进行管理的软件 2、操作系统是提供了处理机管理、 存储器管理…...
【离线数仓-8-数据仓库开发DWD层设计要点-交易域相关事实表】
离线数仓-8-数据仓库开发DWD层设计要点-交易域相关事实表离线数仓-8-数据仓库开发DWD层设计要点-交易域相关事实表一、DWD层设计要点二、交易域相关事实表1.交易域加购事务事实表1.加购事务事实表 前期梳理2.加购事务事实表 DDL表设计分析3.加购事务事实表 加载数据分析1.首日全…...
计算机网络(七):DNS协议和原理,DNS为什么用UDP,网页解析的全过程
文章目录一、什么是DNS二、DNS的作用三、DNS作用四、DNS为什么用UDP五、如果打开一个网站很慢,要如何排查六、网页解析的全过程一、什么是DNS DNS是域名系统的英文缩写,是一种组织成域层次结构的计算机和网络服务命名系统,用于TCP/IP网络。 …...
算法23:多叉树_派对的最大快乐值
公司的每个员工都符合 Employee 类的描述。整个公司的人员结构可以看作是一棵标准的、 没有环的多叉树。树的头节点是公司唯一的老板。除老板之外的每个员工都有唯一的直接上级。 叶节点是没有任何下属的基层员工(subordinates列表为空),除基层员工外,每…...
中国ETC行业市场规模及未来发展趋势
中国ETC行业市场规模及未来发展趋势编辑根据市场调研在线网发布的2023-2029年中国ETC行业发展策略分析及战略咨询研究报告分析:随着政府坚持实施绿色出行政策,ETC行业也受到了极大的支持。根据中国智能交通协会统计,2017年中国ETC行业市场规模…...
每日刷题(一)——只出现一次的数字
前言 今天遇到一个位运算的题目,感觉很有意思,记录一下。 Question1 136. 只出现一次的数字 给你一个 非空 整数数组 nums ,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。 你必须设计并实…...
51c自动驾驶~合集58
我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留,CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制(CCA-Attention),…...
day52 ResNet18 CBAM
在深度学习的旅程中,我们不断探索如何提升模型的性能。今天,我将分享我在 ResNet18 模型中插入 CBAM(Convolutional Block Attention Module)模块,并采用分阶段微调策略的实践过程。通过这个过程,我不仅提升…...
解锁数据库简洁之道:FastAPI与SQLModel实战指南
在构建现代Web应用程序时,与数据库的交互无疑是核心环节。虽然传统的数据库操作方式(如直接编写SQL语句与psycopg2交互)赋予了我们精细的控制权,但在面对日益复杂的业务逻辑和快速迭代的需求时,这种方式的开发效率和可…...
HTML 列表、表格、表单
1 列表标签 作用:布局内容排列整齐的区域 列表分类:无序列表、有序列表、定义列表。 例如: 1.1 无序列表 标签:ul 嵌套 li,ul是无序列表,li是列表条目。 注意事项: ul 标签里面只能包裹 li…...
最新SpringBoot+SpringCloud+Nacos微服务框架分享
文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的,根据Excel列的需求预估的工时直接打骨折,不要问我为什么,主要…...
【项目实战】通过多模态+LangGraph实现PPT生成助手
PPT自动生成系统 基于LangGraph的PPT自动生成系统,可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析:自动解析Markdown文档结构PPT模板分析:分析PPT模板的布局和风格智能布局决策:匹配内容与合适的PPT布局自动…...
【HTTP三个基础问题】
面试官您好!HTTP是超文本传输协议,是互联网上客户端和服务器之间传输超文本数据(比如文字、图片、音频、视频等)的核心协议,当前互联网应用最广泛的版本是HTTP1.1,它基于经典的C/S模型,也就是客…...
【MATLAB代码】基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),附源代码|订阅专栏后可直接查看
文章所述的代码实现了基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),针对传感器观测数据中存在的脉冲型异常噪声问题,通过非线性加权机制提升滤波器的抗干扰能力。代码通过对比传统KF与MCC-KF在含异常值场景下的表现,验证了后者在状态估计鲁棒性方面的显著优…...
MySQL:分区的基本使用
目录 一、什么是分区二、有什么作用三、分类四、创建分区五、删除分区 一、什么是分区 MySQL 分区(Partitioning)是一种将单张表的数据逻辑上拆分成多个物理部分的技术。这些物理部分(分区)可以独立存储、管理和优化,…...
Scrapy-Redis分布式爬虫架构的可扩展性与容错性增强:基于微服务与容器化的解决方案
在大数据时代,海量数据的采集与处理成为企业和研究机构获取信息的关键环节。Scrapy-Redis作为一种经典的分布式爬虫架构,在处理大规模数据抓取任务时展现出强大的能力。然而,随着业务规模的不断扩大和数据抓取需求的日益复杂,传统…...
