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

代码随想录算法训练营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. 修剪二叉搜索树 题目链接 文章链接 前言 本题承接昨天二叉搜索树的插入和删除操作题目&#xff0c;要对整棵二叉搜索树…...

乱 弹 篇(一)

题记 对于“乱弹”这个词汇的释义&#xff0c;《辞海》上仅有“ 戏曲剧种&#xff0c;亦指声腔 ”8个字。而由于“乱弹 ”的“ 弹”谐音谈”&#xff0c;这就容易让人联想到“乱谈”。不过从文体上看&#xff0c;“乱谈”也非乱七八糟之谈&#xff0c;反倒是“东西南北&#x…...

《JVM由浅入深学习【八】 2024-01-12》JVM由简入深学习提升分(JVM的垃圾回收算法)

目录 JVM的垃圾回收算法1. 标记-清除算法&#xff08;Mark-Sweep&#xff09;原理步骤优点缺点 2. 复制算法&#xff08;Copying&#xff09;原理步骤优点缺点 3. 标记-整理算法&#xff08;Mark-Compact&#xff09;原理步骤优点缺点 4. 分代收集算法&#xff08;Generational…...

在矩阵回溯中进行累加和比较的注意点

1 总结 在回溯时&#xff0c;如果递归函数采用void返回&#xff0c;在入口处使用了sum变量&#xff0c;那么一般在初次调用dfs的地方&#xff0c;这个sum的初始值可能不是0,而是数组的对应指针的值&#xff0c;在比较操作的时候&#xff0c;需要在for循环开始之前进行&#xf…...

AI语音机器人的发展

第一代AI语音机器人具体投入研发的开始时间不太清楚&#xff0c;只记得2017年的下半年就已经开始接触到成型的AI语音机器人&#xff0c;并且正式商用。语音识别效果还不多&#xff0c;大多都是接入的科大讯飞或者百度的ASR。 2018年算是AI语音机器人的“青春期”吧&#xff0c;…...

SQL语句错误this is incompatible with sql_mode=only_full_group_by解决方法

一、原理层面 这个错误发生在mysql 5.7.5 版本及以上版本会出现的问题&#xff1a; mysql 5.7.5版本以上默认的sql配置是:sql_mode“ONLY_FULL_GROUP_BY”&#xff0c;这个配置严格执行了"SQL92标准"。 很多从5.6升级到5.7时&#xff0c;为了语法兼容&#xff0c;大部…...

静态长效代理IP和动态短效代理IP有哪些用途?分别适用场景是什么?

静态长效代理IP和动态短效代理IP是两种常见的代理IP类型&#xff0c;它们在用途和适用场景上存在一定的差异。了解它们的特性以及使用场景有助于我们更好地利用代理IP&#xff0c;提高网络访问的效率和安全性。 一、静态长效代理IP 1. 用途 静态长效代理IP是指长期保持稳定的代…...

基于Spring Boot+Vue的课堂管理系统(前后端分离)

该项目完全免费 介绍 基于Spring BootVue的课堂管理系统。前后端分离。包含教师授课管理、学生选退课、聊天室、签到、笔记管理模块等。 技术架构 SpringBoot MyBatis Redis WebSocket VueCLI Axios Element UI 项目特点&#xff1a; 1、后台使用MyBatis连接数据库&…...

供排水管网管理信息化的必要性

供排水管网是城市供水系统的大动脉&#xff0c;它负担者将优质水源输送到最终用户的重要职责&#xff0c;对供水系统有着极其重要的作用。城市供排水管网埋设在地下&#xff0c;规模庞大&#xff0c;仅靠人工难以管理。同时&#xff0c;由于城市的发展&#xff0c;管网连接结构…...

统一格式,无限创意:高效管理不同格式图片批量转换

在数字时代&#xff0c;图片格式的多样性带来了管理上的不便。为了满足不同的需求&#xff0c;我们经常需要将大量图片转换为统一的格式。那么&#xff0c;有没有一种简单、高效的方法来解决这个问题呢&#xff1f;答案是肯定的&#xff01;今天&#xff0c;我们将为您介绍一款…...

工作电压范围宽的国产音频限幅器D2761用于蓝牙音箱,输出噪声最大仅-90dBV

近年来随着相关技术的不断提升&#xff0c;音箱也逐渐从传统的音箱向智能音箱、无线音箱升级。同时在消费升级的背景下&#xff0c;智能音箱成为人们提升生活品质的方式之一。智能音箱是智能化和语音交互技术的产物&#xff0c;具有点歌、购物、控制智能家居设备等功能&#xf…...

中国智造闪耀CES | 木牛科技在美国CES展亮相多领域毫米波雷达尖端方案

素有全球科技潮流“风向标”之称的2024国际消费类电子产品展&#xff08;CES&#xff09;&#xff0c;于1月9-12日在美国拉斯维加斯会议中心举办。CES是全球最大的消费电子和消费技术展览会之一&#xff0c;汇集了世界各地优秀的消费电子和科技公司&#xff0c;带着最好的产品来…...

亚马逊衣物收纳 梳妆台 收纳柜CPC认证ASTM F2057-23 报告分析

衣物收纳商品是指带有抽屉或铰链门的家具商品&#xff0c;通常是卧室家具&#xff0c;用于存放衣物。该政策适用于独立式服装收纳商品 包括但不限于箱子、五斗橱、抽屉柜、大橱柜、衣橱柜、衣橱、门柜和梳妆台&#xff0c;并且满足以下要求&#xff1a; 衣物收纳商品是指带有抽…...

【设计模式】02-SOLID 设计原则

面向对象编程&#xff08;OOP&#xff09;是一种广泛应用的编程范式&#xff0c;它鼓励开发者通过对象来模拟现实世界。为了提高面向对象设计&#xff08;OOD&#xff09;的质量和可维护性&#xff0c;Robert C. Martin提出了 SOLID 原则&#xff0c;这五个原则构成了编写良好、…...

突然间我懂了软件

什么是 “遗留代码” – 它是一个不再由具有这些代码相关理论的人维护的代码库。 单枪匹马的工程师能做出比同样有能力的专业团队更好的产品。单干的工程师会花时间为自己的程序建立一套完整的理论&#xff0c;而专业人员则会定期在不同的项目之间流动&#xff0c;他们只对自己…...

游戏美术的技与艺

大家好&#xff0c;我是阿赵。   可能很多朋友都知道&#xff0c;我刚进入游戏行业的时候&#xff0c;做的是美术工作&#xff0c;包括了建模、贴图、动画等&#xff0c;都做过。我对各种美术资源制作也都很熟悉&#xff0c;懂得很多制作的技术。但最后&#xff0c;我却没有继…...

Python(35):Python3 通过https上传文件和下载文件

Python(35):Python3 通过https上传文件和下载文件 Python http方式的下载&#xff0c;参考&#xff1a;https://blog.csdn.net/fen_fen/article/details/113753983 https需要先安装需要的模块 1、上传示例 1.1、调用&#xff1a; upload_strategy(access_token,"1234…...

【MySQL】日期格式为 YYYY-MM 无法直接使用 DATE_SUB 函数的解决方案(特殊处理 或 PERIOD_DIFF 函数)

力扣题 1、题目地址 1843. 可疑银行账户 2、模拟表 表&#xff1a;Accounts Column NameTypeaccount_idintmax_incomeint account_id 是这张表具有唯一值的列。每行包含一个银行账户每月最大收入的信息。 表&#xff1a;Transactions Column NameTypetransaction_idint…...

Redis的key淘汰方式和内存不足淘汰方式

Redis的key过期淘汰方式 Redis key过期策略 定期删除惰性删除 Redis如何淘汰过期的key 定期删除 隔一段时间&#xff0c;就随机抽取一些设置了过期时间的key&#xff0c;检查其是否过期&#xff0c;如果过期就删除定期删除可能会导致很多过期key到了时间并没有被删除掉&#x…...

java使用redis

1、pom.xml文件里面增加如下依赖&#xff1a; <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-data-redis</artifactId> </dependency> 2、yml文件增加如下配置&#xff1a; redis:host: loc…...

C++实现分布式网络通信框架RPC(3)--rpc调用端

目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中&#xff0c;我们已经大致实现了rpc服务端的各项功能代…...

Cursor实现用excel数据填充word模版的方法

cursor主页&#xff1a;https://www.cursor.com/ 任务目标&#xff1a;把excel格式的数据里的单元格&#xff0c;按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例&#xff0c;…...

【Oracle APEX开发小技巧12】

有如下需求&#xff1a; 有一个问题反馈页面&#xff0c;要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据&#xff0c;方便管理员及时处理反馈。 我的方法&#xff1a;直接将逻辑写在SQL中&#xff0c;这样可以直接在页面展示 完整代码&#xff1a; SELECTSF.FE…...

Nuxt.js 中的路由配置详解

Nuxt.js 通过其内置的路由系统简化了应用的路由配置&#xff0c;使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...

实现弹窗随键盘上移居中

实现弹窗随键盘上移的核心思路 在Android中&#xff0c;可以通过监听键盘的显示和隐藏事件&#xff0c;动态调整弹窗的位置。关键点在于获取键盘高度&#xff0c;并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...

mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包

文章目录 现象&#xff1a;mysql已经安装&#xff0c;但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时&#xff0c;可能是因为以下几个原因&#xff1a;1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...

20个超级好用的 CSS 动画库

分享 20 个最佳 CSS 动画库。 它们中的大多数将生成纯 CSS 代码&#xff0c;而不需要任何外部库。 1.Animate.css 一个开箱即用型的跨浏览器动画库&#xff0c;可供你在项目中使用。 2.Magic Animations CSS3 一组简单的动画&#xff0c;可以包含在你的网页或应用项目中。 3.An…...

AD学习(3)

1 PCB封装元素组成及简单的PCB封装创建 封装的组成部分&#xff1a; &#xff08;1&#xff09;PCB焊盘&#xff1a;表层的铜 &#xff0c;top层的铜 &#xff08;2&#xff09;管脚序号&#xff1a;用来关联原理图中的管脚的序号&#xff0c;原理图的序号需要和PCB封装一一…...

ArcPy扩展模块的使用(3)

管理工程项目 arcpy.mp模块允许用户管理布局、地图、报表、文件夹连接、视图等工程项目。例如&#xff0c;可以更新、修复或替换图层数据源&#xff0c;修改图层的符号系统&#xff0c;甚至自动在线执行共享要托管在组织中的工程项。 以下代码展示了如何更新图层的数据源&…...

计算机系统结构复习-名词解释2

1.定向&#xff1a;在某条指令产生计算结果之前&#xff0c;其他指令并不真正立即需要该计算结果&#xff0c;如果能够将该计算结果从其产生的地方直接送到其他指令中需要它的地方&#xff0c;那么就可以避免停顿。 2.多级存储层次&#xff1a;由若干个采用不同实现技术的存储…...