代码随想录算法训练营Day23|669. 修剪二叉搜索树、108.将有序数组转换为二叉搜索树、538.把二叉搜索树转换为累加树
目录
669. 修剪二叉搜索树
前言
思路
递归法
108.将有序数组转换为二叉搜索树
前言
递归法
538.把二叉搜索树转换为累加树
前言
递归法
总结
669. 修剪二叉搜索树
题目链接
文章链接
前言
本题承接昨天二叉搜索树的插入和删除操作题目,要对整棵二叉搜索树进行遍历修剪。
思路
因为要遍历整棵二叉搜索树,因此不需要返回值也可以,我们可以完成修剪的操作,但是有返回值更方便,可以通过递归函数的返回值来移除节点。
递归法
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* trimBST(TreeNode* root, int low, int high) {if (root == NULL) return NULL;if (root->val < low){//寻找右子树符合区间的节点TreeNode* right = trimBST(root->right, low, high);return right;}if (root->val > high){//寻找左子树符合区间的节点TreeNode* left = trimBST(root->left, low, high);return left;}root->left = trimBST(root->left, low, high); root->right = trimBST(root->right, low, high); return root; }
};
思路同前几题,依然是通过返回本次节点给上一层,上一层用左右孩子接住下一层的返回值。
108.将有序数组转换为二叉搜索树
题目链接
文章链接
前言
题目强调得到的二叉搜索树必须平衡,因此不可以采用简单的线性结构构造二叉搜索树。要将有序数组的中值作为根节点,左侧作为左子树,右侧作为右子树。
递归法
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
private:TreeNode* traversal(vector<int>& nums, int left, int right){if (left > right) return NULL;int mid = left + (right - left) / 2;TreeNode* root = new TreeNode(nums[mid]);root->left = traversal(nums, left, mid - 1);root->right = traversal(nums, mid + 1, right);return root;}
public:TreeNode* sortedArrayToBST(vector<int>& nums) {TreeNode* root = traversal(nums, 0, nums.size() - 1);return root;}
};
在确定数组中值的时候以及递归时左右边界的确定,要严格根据遵守二分法,本题算法采用左闭右闭的区间形式。
538.把二叉搜索树转换为累加树
题目链接
文章链接
前言
将二叉搜索树转化为累加树本质上和数组逆序累加求和的思路一致,难点在于二叉树的遍历顺序。
递归法
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
private:int pre = 0; //记录前一个节点的数值void traversal(TreeNode* cur){if (cur == NULL) return;traversal(cur->right);cur->val += pre;pre = cur->val;traversal(cur->left);}
public:TreeNode* convertBST(TreeNode* root) {pre = 0;traversal(root);return root;}
};
本题单层递归采用右中左的逆中序遍历顺序。
总结
二叉树正式完结!后期要多回顾总结。
相关文章:
代码随想录算法训练营Day23|669. 修剪二叉搜索树、108.将有序数组转换为二叉搜索树、538.把二叉搜索树转换为累加树
目录 669. 修剪二叉搜索树 前言 思路 递归法 108.将有序数组转换为二叉搜索树 前言 递归法 538.把二叉搜索树转换为累加树 前言 递归法 总结 669. 修剪二叉搜索树 题目链接 文章链接 前言 本题承接昨天二叉搜索树的插入和删除操作题目,要对整棵二叉搜索树…...
乱 弹 篇(一)
题记 对于“乱弹”这个词汇的释义,《辞海》上仅有“ 戏曲剧种,亦指声腔 ”8个字。而由于“乱弹 ”的“ 弹”谐音谈”,这就容易让人联想到“乱谈”。不过从文体上看,“乱谈”也非乱七八糟之谈,反倒是“东西南北&#x…...
《JVM由浅入深学习【八】 2024-01-12》JVM由简入深学习提升分(JVM的垃圾回收算法)
目录 JVM的垃圾回收算法1. 标记-清除算法(Mark-Sweep)原理步骤优点缺点 2. 复制算法(Copying)原理步骤优点缺点 3. 标记-整理算法(Mark-Compact)原理步骤优点缺点 4. 分代收集算法(Generational…...
在矩阵回溯中进行累加和比较的注意点
1 总结 在回溯时,如果递归函数采用void返回,在入口处使用了sum变量,那么一般在初次调用dfs的地方,这个sum的初始值可能不是0,而是数组的对应指针的值,在比较操作的时候,需要在for循环开始之前进行…...
AI语音机器人的发展
第一代AI语音机器人具体投入研发的开始时间不太清楚,只记得2017年的下半年就已经开始接触到成型的AI语音机器人,并且正式商用。语音识别效果还不多,大多都是接入的科大讯飞或者百度的ASR。 2018年算是AI语音机器人的“青春期”吧,…...
SQL语句错误this is incompatible with sql_mode=only_full_group_by解决方法
一、原理层面 这个错误发生在mysql 5.7.5 版本及以上版本会出现的问题: mysql 5.7.5版本以上默认的sql配置是:sql_mode“ONLY_FULL_GROUP_BY”,这个配置严格执行了"SQL92标准"。 很多从5.6升级到5.7时,为了语法兼容,大部…...
静态长效代理IP和动态短效代理IP有哪些用途?分别适用场景是什么?
静态长效代理IP和动态短效代理IP是两种常见的代理IP类型,它们在用途和适用场景上存在一定的差异。了解它们的特性以及使用场景有助于我们更好地利用代理IP,提高网络访问的效率和安全性。 一、静态长效代理IP 1. 用途 静态长效代理IP是指长期保持稳定的代…...
基于Spring Boot+Vue的课堂管理系统(前后端分离)
该项目完全免费 介绍 基于Spring BootVue的课堂管理系统。前后端分离。包含教师授课管理、学生选退课、聊天室、签到、笔记管理模块等。 技术架构 SpringBoot MyBatis Redis WebSocket VueCLI Axios Element UI 项目特点: 1、后台使用MyBatis连接数据库&…...
供排水管网管理信息化的必要性
供排水管网是城市供水系统的大动脉,它负担者将优质水源输送到最终用户的重要职责,对供水系统有着极其重要的作用。城市供排水管网埋设在地下,规模庞大,仅靠人工难以管理。同时,由于城市的发展,管网连接结构…...
统一格式,无限创意:高效管理不同格式图片批量转换
在数字时代,图片格式的多样性带来了管理上的不便。为了满足不同的需求,我们经常需要将大量图片转换为统一的格式。那么,有没有一种简单、高效的方法来解决这个问题呢?答案是肯定的!今天,我们将为您介绍一款…...
工作电压范围宽的国产音频限幅器D2761用于蓝牙音箱,输出噪声最大仅-90dBV
近年来随着相关技术的不断提升,音箱也逐渐从传统的音箱向智能音箱、无线音箱升级。同时在消费升级的背景下,智能音箱成为人们提升生活品质的方式之一。智能音箱是智能化和语音交互技术的产物,具有点歌、购物、控制智能家居设备等功能…...
中国智造闪耀CES | 木牛科技在美国CES展亮相多领域毫米波雷达尖端方案
素有全球科技潮流“风向标”之称的2024国际消费类电子产品展(CES),于1月9-12日在美国拉斯维加斯会议中心举办。CES是全球最大的消费电子和消费技术展览会之一,汇集了世界各地优秀的消费电子和科技公司,带着最好的产品来…...
亚马逊衣物收纳 梳妆台 收纳柜CPC认证ASTM F2057-23 报告分析
衣物收纳商品是指带有抽屉或铰链门的家具商品,通常是卧室家具,用于存放衣物。该政策适用于独立式服装收纳商品 包括但不限于箱子、五斗橱、抽屉柜、大橱柜、衣橱柜、衣橱、门柜和梳妆台,并且满足以下要求: 衣物收纳商品是指带有抽…...
【设计模式】02-SOLID 设计原则
面向对象编程(OOP)是一种广泛应用的编程范式,它鼓励开发者通过对象来模拟现实世界。为了提高面向对象设计(OOD)的质量和可维护性,Robert C. Martin提出了 SOLID 原则,这五个原则构成了编写良好、…...
突然间我懂了软件
什么是 “遗留代码” – 它是一个不再由具有这些代码相关理论的人维护的代码库。 单枪匹马的工程师能做出比同样有能力的专业团队更好的产品。单干的工程师会花时间为自己的程序建立一套完整的理论,而专业人员则会定期在不同的项目之间流动,他们只对自己…...
游戏美术的技与艺
大家好,我是阿赵。 可能很多朋友都知道,我刚进入游戏行业的时候,做的是美术工作,包括了建模、贴图、动画等,都做过。我对各种美术资源制作也都很熟悉,懂得很多制作的技术。但最后,我却没有继…...
Python(35):Python3 通过https上传文件和下载文件
Python(35):Python3 通过https上传文件和下载文件 Python http方式的下载,参考:https://blog.csdn.net/fen_fen/article/details/113753983 https需要先安装需要的模块 1、上传示例 1.1、调用: upload_strategy(access_token,"1234…...
【MySQL】日期格式为 YYYY-MM 无法直接使用 DATE_SUB 函数的解决方案(特殊处理 或 PERIOD_DIFF 函数)
力扣题 1、题目地址 1843. 可疑银行账户 2、模拟表 表:Accounts Column NameTypeaccount_idintmax_incomeint account_id 是这张表具有唯一值的列。每行包含一个银行账户每月最大收入的信息。 表:Transactions Column NameTypetransaction_idint…...
Redis的key淘汰方式和内存不足淘汰方式
Redis的key过期淘汰方式 Redis key过期策略 定期删除惰性删除 Redis如何淘汰过期的key 定期删除 隔一段时间,就随机抽取一些设置了过期时间的key,检查其是否过期,如果过期就删除定期删除可能会导致很多过期key到了时间并没有被删除掉&#x…...
java使用redis
1、pom.xml文件里面增加如下依赖: <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-data-redis</artifactId> </dependency> 2、yml文件增加如下配置: redis:host: loc…...
【Axure高保真原型】引导弹窗
今天和大家中分享引导弹窗的原型模板,载入页面后,会显示引导弹窗,适用于引导用户使用页面,点击完成后,会显示下一个引导弹窗,直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...
网络六边形受到攻击
大家读完觉得有帮助记得关注和点赞!!! 抽象 现代智能交通系统 (ITS) 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 (…...
【kafka】Golang实现分布式Masscan任务调度系统
要求: 输出两个程序,一个命令行程序(命令行参数用flag)和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽,然后将消息推送到kafka里面。 服务端程序: 从kafka消费者接收…...
Xshell远程连接Kali(默认 | 私钥)Note版
前言:xshell远程连接,私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...
mongodb源码分析session执行handleRequest命令find过程
mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程,并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令,把数据流转换成Message,状态转变流程是:State::Created 》 St…...
基于Uniapp开发HarmonyOS 5.0旅游应用技术实践
一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架,支持"一次开发,多端部署",可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务,为旅游应用带来…...
376. Wiggle Subsequence
376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...
el-switch文字内置
el-switch文字内置 效果 vue <div style"color:#ffffff;font-size:14px;float:left;margin-bottom:5px;margin-right:5px;">自动加载</div> <el-switch v-model"value" active-color"#3E99FB" inactive-color"#DCDFE6"…...
linux arm系统烧录
1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 (忘了有没有这步了 估计有) 刷机程序 和 镜像 就不提供了。要刷的时…...
c#开发AI模型对话
AI模型 前面已经介绍了一般AI模型本地部署,直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型,但是目前国内可能使用不多,至少实践例子很少看见。开发训练模型就不介绍了&am…...
