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

MySQL技能树

MySQL作为一款广泛使用的关系型数据库管理系统&#xff0c;提供了丰富多样的SQL语句以支持数据的创建、查询、更新和删除等操作。以下是一份MySQL语句操作大全的概览&#xff0c;涵盖从数据库管理到复杂查询的常用命令&#xff1a; ### 一、数据库管理&#xff08;DDL - 数据定…...

redis获取过期时间

03&#xff0c;redisTemplate_redistemplate 获取剩余时间-CSDN博客 11.返回当前key所对应的剩余过期时间 redisTemplate.getExpire(key);1 12.返回剩余过期时间并且指定时间单位 redisTemplate.getExpire(key, unit);...

ERROR in Plugin “react“ was conflicted .... 天坑留念-turborepo、eslint plugin

前两天项目代码拉下来&#xff0c;装完依赖启动的时候直接报错&#xff1a; [eslint] Plugin "react" was conflicted between ".eslintrc.js eslint-config-custom eslint-config-alloy/react" and "BaseConfig D:\pan\erp\test\business-servic…...

MergeTwoSortedLists 【合并有序链表】

有种归并排序的感觉 链表好久不用有些生疏了&#xff0c;思想思路是对的&#xff0c;但是代码写出来有问题&#xff0c;。 写完说点感受&#xff1a; 当时在学校学习链表的时候&#xff0c;就了解到链表分为“有头节点”和“无头节点”的链表&#xff0c;所以这里好像就不练&am…...

基于多反应堆的高并发服务器【C/C++/Reactor】(中)HttpRequest模块 解析http请求协议

一、HTTP响应报文格式 HTTP/1.1 200 OK Bdpagetype: 1 Bdqid: 0xf3c9743300024ee4 Cache-Control: private Connection: keep-alive Content-Encoding: gzip Content-Type: text/html;charsetutf-8 Date: Fri, 26 Feb 2021 08:44:35 GMT Expires: Fri, 26 Feb 2021 08:44:35 GM…...

muduo网络库剖析——网络地址InetAddress类

muduo网络库剖析——网络地址InetAddress类 前情从muduo到my_muduo 概要socketaddr_in介绍成员用法 网络地址转换函数 框架与细节成员函数使用方法 源码结尾 前情 从muduo到my_muduo 作为一个宏大的、功能健全的muduo库&#xff0c;考虑的肯定是众多情况是否可以高效满足&…...

什么是本地IP?服务器本地IP有哪些优势?

本地IP是指直接在互联网上分配给服务器或设备的IP地址&#xff0c;而不是通过NAT&#xff08;网络地址转换&#xff09;或 代理等中间设备进行转发。让我们关注本地IP的优势。 1.直接访问&#xff1a;原始IP允许无中间设备转发或代理直接访问服务器或设备。这减少了网络延迟&a…...

Open CASCADE学习|参数化球面的奇异性

参数曲面的奇异性是一个相对复杂的概念&#xff0c;它涉及到参数曲面的几何特性和参数化过程中的一些特殊情况。参数曲面通常用于描述三维空间中的复杂形状&#xff0c;通过参数方程将二维参数域映射到三维空间中。然而&#xff0c;在某些情况下&#xff0c;参数曲面可能会表现…...

基础知识篇(一)Acticity生命周期

Activity 类是 Android 应用的关键组件&#xff0c;而 activity 的启动和组合方式是平台应用模型的基本组成部分。与使用 main() 方法启动应用的编程范式不同&#xff0c;Android 系统会通过调用与其生命周期特定阶段对应的特定回调方法&#xff0c;在 Activity 实例中启动代码…...

Java内存结构

前文&#xff1a; 《Java8之类的加载》 《Java8之类加载机制class源码分析》 写在开头&#xff1a;本文为学习后的总结&#xff0c;可能有不到位的地方&#xff0c;错误的地方&#xff0c;欢迎各位指正。 JVM 在执行 Java 程序的过程中会把它所管理的内存划分为若干个不同的数…...