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

代码随想录算法训练营第二十二天|235. 二叉搜索树的最近公共祖先、701.二叉搜索树中的插入操作、450.删除二叉搜索树中的节点

目录

235. 二叉搜索树的最近公共祖先

1、递归实现

2、迭代法实现

 701.二叉搜索树中的插入操作(递归实现)

450.删除二叉搜索树中的节点(递归实现)


235. 二叉搜索树的最近公共祖先

相对于 二叉树的最近公共祖先 本题就简单一些了,因为 可以利用二叉搜索树的特性。

题目链接/文章讲解:代码随想录

题解思路:

1、递归实现

迭代法和递归法实现的原理一致,其实我觉得这种迭代法本质就是递归的方法,只不过步骤不一样而已!!!

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {while(root != null){if(root.val > p.val && root.val > q.val){TreeNode left = lowestCommonAncestor(root.left,p,q);if(left != null) return left;}else if(root.val < p.val && root.val < q.val){TreeNode right = lowestCommonAncestor(root.right,p,q);if(right != null) return right;}else{return root;}}return null;}
}

2、迭代法实现

迭代法和递归法实现的原理一致,其实我觉得这种迭代法本质就是递归的方法,只不过步骤不一样而已!!!

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {while(root != null){if(root.val > p.val && root.val > q.val){TreeNode left = lowestCommonAncestor(root.left,p,q);if(left != null) return left;}else if(root.val < p.val && root.val < q.val){TreeNode right = lowestCommonAncestor(root.right,p,q);if(right != null) return right;}else{return root;}}return null;}
}

 701.二叉搜索树中的插入操作(递归实现)

本题比想象中的简单,大家可以先自己想一想应该怎么做,然后看视频讲解,就发现 本题为什么比较简单了。

题目链接/文章讲解:代码随想录

题解思路:

多听卡哥视频讲解!!!在二叉树中插入操作就是构造二叉树,一定能在叶子节点找到我们要插入的节点,然后可以根据二叉搜索树的特性比较当前节点的val值和给定的val,直接判断在其左子树还是右子树进行插入操作!!!最后直接返回root节点就好!!!没听卡哥讲解之前,单纯一团糊浆,第一感觉很复杂,又是各种插入方式等等!!!听完卡哥视频讲解完思路还是清晰的,一刷一定要多听,多看,多刷,把思路打开!!!非科班转码确实有点痛苦,真的就颠覆之前没有训练后的思考方法!!!加油吧!!!

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public TreeNode insertIntoBST(TreeNode root, int val) {//第二步:确定终止条件if(root == null) return new TreeNode(val);;//第三步:确定单层处理逻辑if(root.val > val){root.left = insertIntoBST(root.left,val); //直接根据二叉搜索树的特性比较当前节点的val值和给定的val,直接判断在其左子树还是右子树进行插入操作}else if(root.val < val){root.right = insertIntoBST(root.right,val); //直接根据二叉搜索树的特性比较当前节点的val值和给定的val,直接判断在其左子树还是右子树进行插入操作}return root;}}作者:vansven-h
链接:https://leetcode.cn/problems/insert-into-a-binary-search-tree/solution/701er-cha-sou-suo-shu-zhong-de-cha-ru-ca-fj39/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

450.删除二叉搜索树中的节点(递归实现)

相对于 插入操作,本题就有难度了,涉及到改树的结构

题目链接/文章讲解:代码随想录

题解思路:

主要是删除节点的情况存在五种不同情况,需要根据不同情况进行一一处理,具体的5种情况见下方注释代码!!!我想说的是一刷还是要多看、多听卡哥视频、多刷,把方法论掌握的融汇贯通才有资本自己去造轮子,这些都是基础算法,都没掌握怎么去谈更进阶的知识呢!!!

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public TreeNode deleteNode(TreeNode root, int key) {//第二步:确定终止条件,当找到五种不同情况的节点需要删除时,此时就是遍历到的节点就是终止条件,需要及时对找到的节点进行处理才行if(root == null) return null; //第一种情况:没找到要删除的节点,直接返回null值即可else if(root.val == key){     //以下四种情况都是在找到要删除节点的情况下进行讨论的if(root.left == null && root.right == null) return null; //第二种情况:删除的时叶子节点else if(root.left != null && root.right == null) return root.left; //第三种情况:删除左不为空,右为空的节点else if(root.left == null && root.right != null) return root.right;//第四种情况:删除左为空,右不为空的节点else{TreeNode current = root.right;  //第五种情况:删除左不为空,右不为空的节点,根据二叉搜索树的特性,需要一直搜索右子树的左节点,一直其叶节点进行插入while( current.left != null){current = current.left;}current.left = root.left;return root.right;}}//第三步:确定单层处理逻辑,根据二叉树的搜索特性,直接比较当前遍历节点的val值和key值,直接判断在其左子树还是右子树进行删除节点操作if(root.val > key) root.left = deleteNode(root.left,key);else if(root.val < key) root.right = deleteNode(root.right,key);return root;}
}

相关文章:

代码随想录算法训练营第二十二天|235. 二叉搜索树的最近公共祖先、701.二叉搜索树中的插入操作、450.删除二叉搜索树中的节点

目录 235. 二叉搜索树的最近公共祖先 1、递归实现 2、迭代法实现 701.二叉搜索树中的插入操作&#xff08;递归实现&#xff09; 450.删除二叉搜索树中的节点&#xff08;递归实现&#xff09; 235. 二叉搜索树的最近公共祖先 相对于 二叉树的最近公共祖先 本题就简单一些了…...

hbase表出现RIT删除方案

1.删除zookeeper中对应表注册信息 cd /opt/cloudera/parcels/CDH/lib/zookeeper/bin ./zkCli.sh -server node2:2181 --node2为仿真节点&#xff0c;生产需改 deleteall /hbase/table/表名 2.删除hdfs对应表数据 hadoop dfs -rm -r /hbase/data/default/表名 3.删除hbase:met…...

SQL学习(3)

SELECT 语句用于从表中选取数据。 SELECT 列名称 FROM 表名称 SELECT * FROM 表名称关键词 DISTINCT 用于返回唯一不同的值 SELECT DISTINCT 列名称 FROM 表名称WHERE 子句用于规定选择的标准 如需有条件地从表中选取数据&#xff0c;可将 WHERE 子句添加到 SELECT 语句。 S…...

连接型CRM助力医疗企业把“成本中心”变成“利润中心”

在市场竞争日益加剧的情形下&#xff0c;企业获客成本大幅上涨&#xff0c;存量客户的维护和开发开始被重视&#xff0c;售后服务部门的职责在企业中发挥的价值越来越大。因为企业售后服务不仅能帮助客户解决问题的部门&#xff0c;还是客户与企业沟通的桥梁&#xff0c;将客户…...

《Vue.js 设计与实现》—— 03 Vue.js 3 的设计思路

1. 声明式地描述 UI Vue.js 3 是一个声明式的 UI 框架&#xff0c;即用户在使用 Vue.js 3 开发页面时是声明式地描述 UI 的。 编写前端页面涉及的内容如下&#xff1a; DOM 元素&#xff1a;例如是 div 标签还是 a 标签属性&#xff1a;如 a 标签的 href 属性&#xff0c;再…...

2023年湖北省建设厅特种作业操作证报名条件是什么?

建筑施工特种作业人员是指在房屋建筑和市政工程施工活动中&#xff0c;从事可能对本人、他人及周围设备设施的安全造成重大危害作业的人员。建筑施工特种作业人员必须经建设主管部门考核合格&#xff0c;取得建筑施工特种作业人员操作资格证书&#xff08;以下简称“资格证书”…...

Redis 进阶

&#x1f972; &#x1f978; &#x1f90c; &#x1fac0; &#x1fac1; &#x1f977; &#x1f43b;‍❄️&#x1f9a4; &#x1fab6; &#x1f9ad; &#x1fab2; &#x1fab3; &#x1fab0; &#x1fab1; &#x1fab4; &#x1fad0; &#x1fad2; &#x1fad1;…...

伙伴匹配系统笔记---02

Java 8特性 1. stream / parallelStream 流失处理 2. Optional 可选类 一. 前端整合路由 1. 路由:vue 路由组件库地址:安装 | Vue Router (vuejs.org) 安装:yarn add vue-router@4 2. 整合路由: // 1. 定义路由组件. // 也可以从其他文件导入 const Home = { templ…...

Redis学习——单机版安装

目录 1.解压 2.安装gcc 3.执行make命令 4.复制redis的配置文件到默认安装目录下 5.修改redis.conf文件 6.启动redis服务与客户端 7.查看redis进行是否启动 8.关闭redis服务 9.redis性能测试 注意&#xff1a;安装redis前要安装jdk。 1.解压 [rootlxm148 install]# t…...

第三十一章 React中路由组件和一般组件

在React中&#xff0c;组件是应用程序的构建块。它们是可重用的&#xff0c;可以用于创建复杂的UI。React中有两种类型的组件&#xff1a;路由组件和一般组件。 一般组件 一般组件是React应用程序的基本构建块。它们是可重用的&#xff0c;可以用于创建复杂的UI。它们不知道U…...

怎么把pdf中的某一页分出来?

怎么把pdf中的某一页分出来&#xff1f;PDF格式的文档在日常生活中是非常常见的&#xff0c;相信大家都对其有所了解&#xff0c;并且经常使用。它的主要特点是不允许用户随意编辑其中的内容&#xff0c;当我们仅需要阅读时&#xff0c;PDF文档无疑是十分方便的&#xff0c;尤其…...

MongoDB 聚合操作Map-Reduce

这此之前已经对MongoDB中的一些聚合操作进行了详细的介绍&#xff0c;主要介绍了聚合方法和聚合管道&#xff1b;如果您想对聚合方法和聚合管道进行了解&#xff0c;可以参考&#xff1a; MongoDB 数据库操作汇总https://blog.csdn.net/m1729339749/article/details/130086022…...

shiro CVE-2016-4437 漏洞复现

shiro Apache Shiro是一个强大且易用的Java安全框架,执行身份验证、授权、密码和会话管理。使用Shiro的易于理解的API,您可以快速、轻松地获得任何应用程序,从最小的移动应用程序到最大的网络和企业应用程序漏洞原理 在Apache shiro的框架中&#xff0c;执行身份验证时提供了…...

Seqkit-2.2.0 移植指南(openEuler 20.03 LTS SP3)

1.软件介绍 seqkit是一种跨平台的、极快的&#xff0c;全面的fasta/q处理工具。seqkit为所有的主流操作系统提供了一种可执行的双元文件&#xff0c;包括Windows&#xff0c;Linux&#xff0c;MacOS X&#xff0c;并且不依赖于任何的配置或预先配置就可以直接使用。 关于seqk…...

Java版本企业电子招投标采购系统源码——功能模块功能描述+数字化采购管理 采购招投标

功能模块&#xff1a; 待办消息&#xff0c;招标公告&#xff0c;中标公告&#xff0c;信息发布 描述&#xff1a; 全过程数字化采购管理&#xff0c;打造从供应商管理到采购招投标、采购合同、采购执行的全过程数字化管理。通供应商门户具备内外协同的能力&#xff0c;为外部供…...

二十三种设计模式第五篇--原型模式

原型模式&#xff08;Prototype Pattern&#xff09;是用于创建重复的对象&#xff0c;同时又能保证性能。这种类型的设计模式属于创建型模式&#xff0c;它提供了一种创建对象的最佳方式。 这种模式是实现了一个原型接口&#xff0c;该接口用于创建当前对象的克隆。当直接创建…...

阿里云镜像区别公共镜像、自定义、共享、云市场和社区镜像介绍

阿里云服务器镜像根据来源不同分为公共镜像、自定义镜像、共享镜像、云市场镜像和社区镜像&#xff0c;一般没有特殊情况选择公共镜像&#xff0c;公共镜像是阿里云官网提供的正版授权操作系统&#xff0c;云市场镜像是在纯净版操作系统的基础上预装了相关软件及运行环境&#…...

非线性方程二分法

非线性方程二分法 优点&#xff1a;算法直观、简单、总能保证收敛&#xff1b;局限&#xff1a;收敛速度慢、一般不单独用它求根&#xff0c;仅为了获取根的粗略近似 文章目录 非线性方程二分法[toc]1 二分法基本思想2 二分法实现 1 二分法基本思想 设 f ( x ) f(x) f(x)在 [ …...

H3C防火墙单机旁路部署(网关在防火墙)

防火墙旁路部署在核心交换机上&#xff0c;内网有三个网段vlan 10&#xff1a;172.16.10.1/24、vlan 20&#xff1a;172.16.20.1/24、vlan30&#xff1a;172.16.30.1。要求内网网关在防火墙设备上&#xff0c;由防火墙作为DHCP服务器给终端下发地址&#xff0c;同时由防火墙来控…...

基于密度的无线传感器网络聚类算法的博弈分析(Matlab代码实现)

目录 &#x1f4a5;1 概述 &#x1f4da;2 运行结果 &#x1f389;3 参考文献 &#x1f468;‍&#x1f4bb;4 Matlab代码 &#x1f4a5;1 概述 提高能源效率是无线传感器网络面临的关键挑战之一&#xff0c;无线传感器网络日益普遍。由于节点&#xff08;传感器&#xff…...

多模态2025:技术路线“神仙打架”,视频生成冲上云霄

文&#xff5c;魏琳华 编&#xff5c;王一粟 一场大会&#xff0c;聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中&#xff0c;汇集了学界、创业公司和大厂等三方的热门选手&#xff0c;关于多模态的集中讨论达到了前所未有的热度。其中&#xff0c;…...

理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端

&#x1f31f; 什么是 MCP&#xff1f; 模型控制协议 (MCP) 是一种创新的协议&#xff0c;旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议&#xff0c;它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...

【第二十一章 SDIO接口(SDIO)】

第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...

质量体系的重要

质量体系是为确保产品、服务或过程质量满足规定要求&#xff0c;由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面&#xff1a; &#x1f3db;️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限&#xff0c;形成层级清晰的管理网络&#xf…...

【2025年】解决Burpsuite抓不到https包的问题

环境&#xff1a;windows11 burpsuite:2025.5 在抓取https网站时&#xff0c;burpsuite抓取不到https数据包&#xff0c;只显示&#xff1a; 解决该问题只需如下三个步骤&#xff1a; 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...

视频字幕质量评估的大规模细粒度基准

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用&#xff0c;因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型&#xff08;VLMs&#xff09;在字幕生成方面…...

uniapp微信小程序视频实时流+pc端预览方案

方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度​WebSocket图片帧​定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐​RTMP推流​TRTC/即构SDK推流❌ 付费方案 &#xff08;部分有免费额度&#x…...

Axios请求超时重发机制

Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式&#xff1a; 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...

全面解析各类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&#xff1f; IPsec VPN 5.1 IPsec传输模式&#xff08;Transport Mode&#xff09; 5.2 IPsec隧道模式&#xff08;Tunne…...

【生成模型】视频生成论文调研

工作清单 上游应用方向&#xff1a;控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...