算法训练营day22(二叉树08:二叉搜索树的最近公共祖先,插入,删除)
第六章 二叉树part08
今日内容: ● 235. 二叉搜索树的最近公共祖先
● 701.二叉搜索树中的插入操作
● 450.删除二叉搜索树中的节点 详细布置 235. 二叉搜索树的最近公共祖先 相对于 二叉树的最近公共祖先 本题就简单一些了,因为 可以利用二叉搜索树的特性。 题目链接/文章讲解:https://programmercarl.com/0235.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E7%9A%84%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88.html
视频讲解:https://www.bilibili.com/video/BV1Zt4y1F7ww 701.二叉搜索树中的插入操作 本题比想象中的简单,大家可以先自己想一想应该怎么做,然后看视频讲解,就发现 本题为什么比较简单了。题目链接/文章讲解:https://programmercarl.com/0701.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E6%8F%92%E5%85%A5%E6%93%8D%E4%BD%9C.html
视频讲解:https://www.bilibili.com/video/BV1Et4y1c78Y 450.删除二叉搜索树中的节点 相对于 插入操作,本题就有难度了,涉及到改树的结构 题目链接/文章讲解:https://programmercarl.com/0450.%E5%88%A0%E9%99%A4%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E8%8A%82%E7%82%B9.html
视频讲解:https://www.bilibili.com/video/BV1tP41177us 往日任务
● day 1 任务以及具体安排:https://docs.qq.com/doc/DUG9UR2ZUc3BjRUdY
● day 2 任务以及具体安排:https://docs.qq.com/doc/DUGRwWXNOVEpyaVpG
● day 3 任务以及具体安排:https://docs.qq.com/doc/DUGdqYWNYeGhlaVR6
● day 4 任务以及具体安排:https://docs.qq.com/doc/DUFNjYUxYRHRVWklp
● day 5 周日休息
● day 6 任务以及具体安排:https://docs.qq.com/doc/DUEtFSGdreWRuR2p4
● day 7 任务以及具体安排:https://docs.qq.com/doc/DUElCb1NyTVpXa0Jj
● day 8 任务以及具体安排:https://docs.qq.com/doc/DUGdsY2JFaFhDRVZH
● day 9 任务以及具体安排:https://docs.qq.com/doc/DUHVXSnZNaXpVUHN4
● day 10 任务以及具体安排:https://docs.qq.com/doc/DUElqeHh3cndDbW1Q
●day 11 任务以及具体安排:https://docs.qq.com/doc/DUHh6UE5hUUZOZUd0
●day 12 周日休息
●day 13 任务以及具体安排:https://docs.qq.com/doc/DUHNpa3F4b2dMUWJ3
●day 14 任务以及具体安排:https://docs.qq.com/doc/DUHRtdXZZSWFkeGdE
●day 15 任务以及具体安排:https://docs.qq.com/doc/DUHN0ZVJuRmVYeWNv
●day 16 任务以及具体安排:https://docs.qq.com/doc/DUHBQRm1aSWR4T2NK
●day 17 任务以及具体安排:https://docs.qq.com/doc/DUFpXY3hBZkpabWFY
●day 18 任务以及具体安排:https://docs.qq.com/doc/DUFFiVHl3YVlReVlr
●day 19 周日休息
●day 20 任务以及具体安排:https://docs.qq.com/doc/DUGFRU2V6Z1F4alBH
●day 21 任务以及具体安排:https://docs.qq.com/doc/DUHl2SGNvZmxqZm1X
day22
二叉搜索树的最近公共祖先
递归法
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if (root.val > p.val && root.val > q.val) return lowestCommonAncestor(root.left, p, q);if (root.val < p.val && root.val < q.val) return lowestCommonAncestor(root.right, p, q);return root;}}//中左右,遍历到节点立刻返回//在遍历二叉搜索树的时候就是寻找区间[p->val, q->val](注意这里是左闭又闭),如果 cur->val 大于 p->val,同时 cur->val 大于q->val,那么就应该向左遍历(说明目标区间在左子树上)。class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {//if( root == null) return null;if( root.val > p.val && root.val > q.val) {//左遍历TreeNode left = lowestCommonAncestor( root.left , p,q);if( left != null) return left;//找到了就立刻返回}if( root.val < q.val && root.val < p.val){return lowestCommonAncestor(root.right, p,q);}return root;}}
二叉搜索树的插入
递归法
//实际插入都可以找到合适的叶子节点进行插入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);//更新左子树,递归创建if( root.val < val) root.right = insertIntoBST(root.right,val);return root;}}
删除二叉搜索树的节点
递归法
class Solution {public TreeNode deleteNode(TreeNode root, int key) {if( root == null) return root;//没找到直接返回if( root.val == key){//找到了,要删除节点if( root.left== null) return root.right;//情况一二:左右为空,左子树为空else if( root.right == null) return root.left;//情况三:右子树为空else{//情况五:左右不为空TreeNode cur = root.right;while( cur.left != null) {cur = cur.left;}//右子树的最左边节点curcur.left = root.left;return root.right;}}if( root.val > key) root.left = deleteNode(root.left, key);if( root.val < key) root.right = deleteNode( root.right, key);return root;}}
小结:插入和删除的递归方法很像,都是要返回被重新构建的左右子树,先处理终止逻辑然后不需要遍历全部二叉树就直接返回,然后重构左右子树,最后return被重构好的root即可
感谢大佬分享:
代码随想录-算法训练营day22【二叉树08:二叉搜索树的最近公共祖先、二叉搜索树中的插入操作、删除二叉搜索树中的节点】-CSDN博客
相关文章:
算法训练营day22(二叉树08:二叉搜索树的最近公共祖先,插入,删除)
第六章 二叉树part08 今日内容: ● 235. 二叉搜索树的最近公共祖先 ● 701.二叉搜索树中的插入操作 ● 450.删除二叉搜索树中的节点 详细布置 235. 二叉搜索树的最近公共祖先 相对于 二叉树的最近公共祖先 本题就简单一些了,因为 可以利用二叉搜索树的…...
Linux history 命令详解
简介 history 命令显示当前 shell 会话中以前执行过的命令列表。这对于无需重新输入命令即可重新调用或重新执行命令特别有用。 示例用法 显示命令历史列表 history# 示例输出如下:1 ls -l 2 cd /var/log 3 cat syslog执行历史记录中的命令 !<number>…...

Kafka知识体系
一、认识Kafka 1. kafka适用场景 消息系统:kafka不仅具备传统的系统解耦、流量削峰、缓冲、异步通信、可扩展性、可恢复性等功能,还有其他消息系统难以实现的消息顺序消费及消息回溯功能。 存储系统:kafka把消息持久化到磁盘上,…...

【Android】EventBus的使用及源码分析
文章目录 介绍优点基本用法线程模式POSTINGMAINMAIN_ORDEREDBACKGROUNDASYNC 黏性事件 源码注册getDefault()registerfindSubscriberMethods小结 postpostStickyunregister 介绍 优点 简化组件之间的通信 解耦事件发送者和接收者在 Activity、Fragment 和后台线程中表现良好避…...

【大数据学习 | Spark调优篇】Spark之内存调优
1. 内存的花费 1)每个Java对象,都有一个对象头,会占用16个字节,主要是包括了一些对象的元信息,比如指向它的类的指针。如果一个对象本身很小,比如就包括了一个int类型的field,那么它的对象头实…...

Linux:文件系统inode
早期,存储文件的设备是磁盘(当下的市场几乎都是SSD),但大家习惯的把它们都称为磁盘,磁盘是用来表示区分内存的存储设备。而在操作系统看来,这个存储设备的结构就是一个线性结构,这一点很重要。 …...
力扣难题解析
滑动窗口问题 76.最小覆盖子串 题目链接:76. 最小覆盖子串 - 力扣(LeetCode) 题目描述: 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空…...
4.5-Channel 和 Flow:SharedFlow 和 StateFlow
文章目录 SharedFlow数据流的收集和事件订阅的区别launchIn() 和 shareIn() 的区别SharedFlow 与 Flow、Channel 的区别shareIn() 适用场景 shareIn() 的具体参数说明shareIn() 的 replay 参数shareIn() 的 started 参数WhileSubscribed() 的参数及适用场景 MutableSharedFlow、…...
Qt | TCP服务器实现QTcpServer,使用线程管理客户端套接字
点击上方"蓝字"关注我们 01、QTcpServer >>> QTcpServer 是 Qt 网络模块中的一个类,用于实现TCP服务器。它允许创建一个服务器,可以接受来自客户端的连接。QTcpServer 是事件驱动的,这意味着它将通过信号和槽机制处理网络事件。 常用函数 构造函数: QT…...

【提高篇】3.6 GPIO(六,寄存器介绍,下)
目录 2.3 输出速度寄存器OSPEEDR(GPIOx_OSPEEDR) (x = A..I) 2.4 上拉/下拉寄存器 (GPIOx_PUPDR) (x = A..I) 2.5 输入数据寄存器(IDR) 2.6 输出数据寄存器(ODR) 2.7 置位/复位寄存器(BSRR) 2.8 BSRR与ODR寄存器的区别 2.3 输出速度寄存器OSPEEDR(GPIOx_OSPEEDR) (…...

【AI】数据,算力,算法和应用(3)
三、算法 算法这个词,我们都不陌生。 从接触计算机,就知道有“算法”这样一个神秘的名词存在。象征着专业、权威、神秘、高难等等。 算法是一组有序的解决问题的规则和指令,用于解决特定问题的一系列步骤。算法可以被看作是解决问题的方法…...

深度学习笔记——生成对抗网络GAN
本文详细介绍早期生成式AI的代表性模型:生成对抗网络GAN。 文章目录 一、基本结构生成器判别器 二、损失函数判别器生成器交替优化目标函数 三、GAN 的训练过程训练流程概述训练流程步骤1. 初始化参数和超参数2. 定义损失函数3. 训练过程的迭代判别器训练步骤生成器…...
网络安全开源组件
本文只是针对开源项目进行收集,如果后期在工作中碰到其他开源项目将进行更新。欢迎大家在评论区留言,您在工作碰到的开源项目。 祝您工作顺利,鹏程万里! 一、FW(防火墙) 1.1 pfSense pfSense项目是一个免费…...

Python毕业设计选题:基于django+vue的智慧社区可视化平台的设计与实现+spider
开发语言:Python框架:djangoPython版本:python3.7.7数据库:mysql 5.7数据库工具:Navicat11开发软件:PyCharm 系统展示 管理员登录 管理员功能界面 养老机构管理 业主管理 社区安防管理 社区设施管理 车位…...

Oracle LinuxR7安装Oracle 12.2 RAC集群实施(DNS解析)
oracleLinuxR7-U6系统Oracle 12.2 RAC集群实施(DNS服务器) 环境 RAC1RAC2DNS服务器操作系统Oracle LinuxR7Oracle LinuxR7windows server 2008R2IP地址172.30.21.101172.30.21.102172.30.21.112主机名称hefei1hefei2hefei数据库名hefeidbhefeidb实例名…...

M2芯片安装es的步骤
背景:因为最近经常用到es,但是测试环境没有es,自己本地也没安装,为了方便测试,然后安装一下,但是刚开始安装就报错,记录一下,安装的版本为8.16.1 第一步:去官网下载maco…...

macos下brew安装redis
首先确保已安装brew,接下来搜索资源,在终端输入如下命令: brew search redis 演示如下: 如上看到有redis资源,下面进行安装,执行下面的命令: brew install redis 演示效果如下: …...

第六届金盾信安杯-SSRF
操作内容: 进入环境 可以查询网站信息 查询环境url https://114.55.67.167:52263/flag.php 返回 flag 就在这 https://114.55.67.167:52263/flag.php 把这个转换成短连接,然后再提交 得出 flag...

【论文投稿】国产游戏技术:迈向全球引领者的征途
【IEEE出版南方科技大学】第十一届电气工程与自动化国际会议(IFEEA 2024)_艾思科蓝_学术一站式服务平台 更多学术会议论文投稿请看:https://ais.cn/u/nuyAF3 目录 国产游戏技术能否引领全球? 一、国产游戏技术的崛起之路 1.1 初期探索与积…...
腾讯微众银行大数据面试题(包含数据分析/挖掘方向)面试题及参考答案
为什么喜欢使用 XGBoost,XGBoost 的主要优势有哪些? XGBoost 是一个优化的分布式梯度增强库,在数据科学和机器学习领域应用广泛,深受喜爱,原因主要在于其众多突出优势。 首先,它的精度高,在许多机器学习竞赛和实际应用中,XGBoost 都展现出卓越的预测准确性。其基于决策…...

使用VSCode开发Django指南
使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架,专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用,其中包含三个使用通用基本模板的页面。在此…...
【杂谈】-递归进化:人工智能的自我改进与监管挑战
递归进化:人工智能的自我改进与监管挑战 文章目录 递归进化:人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管?3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...

高危文件识别的常用算法:原理、应用与企业场景
高危文件识别的常用算法:原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件,如包含恶意代码、敏感数据或欺诈内容的文档,在企业协同办公环境中(如Teams、Google Workspace)尤为重要。结合大模型技术&…...
【AI学习】三、AI算法中的向量
在人工智能(AI)算法中,向量(Vector)是一种将现实世界中的数据(如图像、文本、音频等)转化为计算机可处理的数值型特征表示的工具。它是连接人类认知(如语义、视觉特征)与…...
vue3 定时器-定义全局方法 vue+ts
1.创建ts文件 路径:src/utils/timer.ts 完整代码: import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...

ElasticSearch搜索引擎之倒排索引及其底层算法
文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...
OpenLayers 分屏对比(地图联动)
注:当前使用的是 ol 5.3.0 版本,天地图使用的key请到天地图官网申请,并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能,和卷帘图层不一样的是,分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...

C# 求圆面积的程序(Program to find area of a circle)
给定半径r,求圆的面积。圆的面积应精确到小数点后5位。 例子: 输入:r 5 输出:78.53982 解释:由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982,因为我们只保留小数点后 5 位数字。 输…...

JVM 内存结构 详解
内存结构 运行时数据区: Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器: 线程私有,程序控制流的指示器,分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 每个线程都有一个程序计数…...

Python Ovito统计金刚石结构数量
大家好,我是小马老师。 本文介绍python ovito方法统计金刚石结构的方法。 Ovito Identify diamond structure命令可以识别和统计金刚石结构,但是无法直接输出结构的变化情况。 本文使用python调用ovito包的方法,可以持续统计各步的金刚石结构,具体代码如下: from ovito…...