当前位置: 首页 > 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 都展现出卓越的预测准确性。其基于决策…...

docker详细操作--未完待续

docker介绍 docker官网: Docker&#xff1a;加速容器应用程序开发 harbor官网&#xff1a;Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台&#xff0c;用于将应用程序及其依赖项&#xff08;如库、运行时环…...

Cesium1.95中高性能加载1500个点

一、基本方式&#xff1a; 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...

Qt Widget类解析与代码注释

#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码&#xff0c;写上注释 当然可以&#xff01;这段代码是 Qt …...

【大模型RAG】Docker 一键部署 Milvus 完整攻略

本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装&#xff1b;只需暴露 19530&#xff08;gRPC&#xff09;与 9091&#xff08;HTTP/WebUI&#xff09;两个端口&#xff0c;即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...

【git】把本地更改提交远程新分支feature_g

创建并切换新分支 git checkout -b feature_g 添加并提交更改 git add . git commit -m “实现图片上传功能” 推送到远程 git push -u origin feature_g...

均衡后的SNRSINR

本文主要摘自参考文献中的前两篇&#xff0c;相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程&#xff0c;其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt​ 根发送天线&#xff0c; n r n_r nr​ 根接收天线的 MIMO 系…...

C++使用 new 来创建动态数组

问题&#xff1a; 不能使用变量定义数组大小 原因&#xff1a; 这是因为数组在内存中是连续存储的&#xff0c;编译器需要在编译阶段就确定数组的大小&#xff0c;以便正确地分配内存空间。如果允许使用变量来定义数组的大小&#xff0c;那么编译器就无法在编译时确定数组的大…...

人工智能(大型语言模型 LLMs)对不同学科的影响以及由此产生的新学习方式

今天是关于AI如何在教学中增强学生的学习体验&#xff0c;我把重要信息标红了。人文学科的价值被低估了 ⬇️ 转型与必要性 人工智能正在深刻地改变教育&#xff0c;这并非炒作&#xff0c;而是已经发生的巨大变革。教育机构和教育者不能忽视它&#xff0c;试图简单地禁止学生使…...

招商蛇口 | 执笔CID,启幕低密生活新境

作为中国城市生长的力量&#xff0c;招商蛇口以“美好生活承载者”为使命&#xff0c;深耕全球111座城市&#xff0c;以央企担当匠造时代理想人居。从深圳湾的开拓基因到西安高新CID的战略落子&#xff0c;招商蛇口始终与城市发展同频共振&#xff0c;以建筑诠释对土地与生活的…...

免费PDF转图片工具

免费PDF转图片工具 一款简单易用的PDF转图片工具&#xff0c;可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件&#xff0c;也不需要在线上传文件&#xff0c;保护您的隐私。 工具截图 主要特点 &#x1f680; 快速转换&#xff1a;本地转换&#xff0c;无需等待上…...