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

算法训练营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 今日内容&#xff1a; ● 235. 二叉搜索树的最近公共祖先 ● 701.二叉搜索树中的插入操作 ● 450.删除二叉搜索树中的节点 详细布置 235. 二叉搜索树的最近公共祖先 相对于 二叉树的最近公共祖先 本题就简单一些了&#xff0c;因为 可以利用二叉搜索树的…...

Linux history 命令详解

简介 history 命令显示当前 shell 会话中以前执行过的命令列表。这对于无需重新输入命令即可重新调用或重新执行命令特别有用。 示例用法 显示命令历史列表 history# 示例输出如下&#xff1a;1 ls -l 2 cd /var/log 3 cat syslog执行历史记录中的命令 !<number>…...

Kafka知识体系

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

【Android】EventBus的使用及源码分析

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

【大数据学习 | Spark调优篇】Spark之内存调优

1. 内存的花费 1&#xff09;每个Java对象&#xff0c;都有一个对象头&#xff0c;会占用16个字节&#xff0c;主要是包括了一些对象的元信息&#xff0c;比如指向它的类的指针。如果一个对象本身很小&#xff0c;比如就包括了一个int类型的field&#xff0c;那么它的对象头实…...

Linux:文件系统inode

早期&#xff0c;存储文件的设备是磁盘&#xff08;当下的市场几乎都是SSD&#xff09;&#xff0c;但大家习惯的把它们都称为磁盘&#xff0c;磁盘是用来表示区分内存的存储设备。而在操作系统看来&#xff0c;这个存储设备的结构就是一个线性结构&#xff0c;这一点很重要。 …...

力扣难题解析

滑动窗口问题 76.最小覆盖子串 题目链接&#xff1a;76. 最小覆盖子串 - 力扣&#xff08;LeetCode&#xff09; 题目描述&#xff1a; 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串&#xff0c;则返回空…...

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)

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

深度学习笔记——生成对抗网络GAN

本文详细介绍早期生成式AI的代表性模型&#xff1a;生成对抗网络GAN。 文章目录 一、基本结构生成器判别器 二、损失函数判别器生成器交替优化目标函数 三、GAN 的训练过程训练流程概述训练流程步骤1. 初始化参数和超参数2. 定义损失函数3. 训练过程的迭代判别器训练步骤生成器…...

网络安全开源组件

本文只是针对开源项目进行收集&#xff0c;如果后期在工作中碰到其他开源项目将进行更新。欢迎大家在评论区留言&#xff0c;您在工作碰到的开源项目。 祝您工作顺利&#xff0c;鹏程万里&#xff01; 一、FW&#xff08;防火墙&#xff09; 1.1 pfSense pfSense项目是一个免费…...

Python毕业设计选题:基于django+vue的智慧社区可视化平台的设计与实现+spider

开发语言&#xff1a;Python框架&#xff1a;djangoPython版本&#xff1a;python3.7.7数据库&#xff1a;mysql 5.7数据库工具&#xff1a;Navicat11开发软件&#xff1a;PyCharm 系统展示 管理员登录 管理员功能界面 养老机构管理 业主管理 社区安防管理 社区设施管理 车位…...

Oracle LinuxR7安装Oracle 12.2 RAC集群实施(DNS解析)

oracleLinuxR7-U6系统Oracle 12.2 RAC集群实施&#xff08;DNS服务器&#xff09; 环境 RAC1RAC2DNS服务器操作系统Oracle LinuxR7Oracle LinuxR7windows server 2008R2IP地址172.30.21.101172.30.21.102172.30.21.112主机名称hefei1hefei2hefei数据库名hefeidbhefeidb实例名…...

M2芯片安装es的步骤

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

macos下brew安装redis

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

第六届金盾信安杯-SSRF

操作内容&#xff1a; 进入环境 可以查询网站信息 查询环境url https://114.55.67.167:52263/flag.php 返回 flag 就在这 https://114.55.67.167:52263/flag.php 把这个转换成短连接&#xff0c;然后再提交 得出 flag...

【论文投稿】国产游戏技术:迈向全球引领者的征途

【IEEE出版南方科技大学】第十一届电气工程与自动化国际会议&#xff08;IFEEA 2024)_艾思科蓝_学术一站式服务平台 更多学术会议论文投稿请看&#xff1a;https://ais.cn/u/nuyAF3 目录 国产游戏技术能否引领全球&#xff1f; 一、国产游戏技术的崛起之路 1.1 初期探索与积…...

腾讯微众银行大数据面试题(包含数据分析/挖掘方向)面试题及参考答案

为什么喜欢使用 XGBoost,XGBoost 的主要优势有哪些? XGBoost 是一个优化的分布式梯度增强库,在数据科学和机器学习领域应用广泛,深受喜爱,原因主要在于其众多突出优势。 首先,它的精度高,在许多机器学习竞赛和实际应用中,XGBoost 都展现出卓越的预测准确性。其基于决策…...

使用VSCode开发Django指南

使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架&#xff0c;专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用&#xff0c;其中包含三个使用通用基本模板的页面。在此…...

【杂谈】-递归进化:人工智能的自我改进与监管挑战

递归进化&#xff1a;人工智能的自我改进与监管挑战 文章目录 递归进化&#xff1a;人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管&#xff1f;3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...

高危文件识别的常用算法:原理、应用与企业场景

高危文件识别的常用算法&#xff1a;原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件&#xff0c;如包含恶意代码、敏感数据或欺诈内容的文档&#xff0c;在企业协同办公环境中&#xff08;如Teams、Google Workspace&#xff09;尤为重要。结合大模型技术&…...

【AI学习】三、AI算法中的向量

在人工智能&#xff08;AI&#xff09;算法中&#xff0c;向量&#xff08;Vector&#xff09;是一种将现实世界中的数据&#xff08;如图像、文本、音频等&#xff09;转化为计算机可处理的数值型特征表示的工具。它是连接人类认知&#xff08;如语义、视觉特征&#xff09;与…...

vue3 定时器-定义全局方法 vue+ts

1.创建ts文件 路径&#xff1a;src/utils/timer.ts 完整代码&#xff1a; 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 分屏对比(地图联动)

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能&#xff0c;和卷帘图层不一样的是&#xff0c;分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...

C# 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

JVM 内存结构 详解

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

Python Ovito统计金刚石结构数量

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