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

【LeetCode+JavaGuide打卡】Day22|235. 二叉搜索树的最近公共祖先、701.二叉搜索树中的插入操作、450.删除二叉搜索树中的节点

学习目标:

  • 235. 二叉搜索树的最近公共祖先
  • 701.二叉搜索树中的插入操作
  • 450.删除二叉搜索树中的节点

学习内容:

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

题目链接&&文章讲解
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。

//递归法
//从上向下去递归遍历,第一次遇到 cur节点是数值在[q, p]区间中,那么cur就是 q和p的最近公共祖先。
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 < p.val && root.val < q.val) {TreeNode right = lowestCommonAncestor(root.right, p, q);if(right != null) return right;}return root;}
}//迭代法
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {TreeNode cur = root;while(cur != null){if(cur.val > p.val && cur.val > q.val)  cur = cur.left;else if(cur.val < p.val && cur.val < q.val)  cur = cur.right;else return cur;}return null;}
}

701.二叉搜索树中的插入操作

题目链接&&文章讲解

//在叶子节点找到插入位置
class Solution {public TreeNode insertIntoBST(TreeNode root, int val) {//终止条件if(root == null) {TreeNode node = new TreeNode(val);return node;}//左if(val < root.val){root.left = insertIntoBST(root.left, val);}//右if(val > root.val){root.right = insertIntoBST(root.right, val);}return root;}
}

450.删除二叉搜索树中的节点

题目链接&&文章讲解

有以下五种情况:

  • 第一种情况:没找到删除的节点,遍历到空节点直接返回了找到删除的节点
  • 第二种情况:左右孩子都为空(叶子节点),直接删除节点, 返回NULL为根节点
  • 第三种情况:删除节点的左孩子为空,右孩子不为空,删除节点,右孩子补位,返回右孩子为根节点
  • 第四种情况:删除节点的右孩子为空,左孩子不为空,删除节点,左孩子补位,返回左孩子为根节点
  • 第五种情况:左右孩子节点都不为空,则将删除节点的左子树头结点(左孩子)放到删除节点的右子树的最左面节点的左孩子上,返回删除节点右孩子为新的根节点。
class Solution {public TreeNode deleteNode(TreeNode root, int key) {//终止条件//没有找到删除节点if(root == null) return null;//找到要删除的节点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 cur = root.right;while(cur.left != null) cur = cur.left;cur.left = root.left;return root.right;}}//处理逻辑if(key < root.val){root.left = deleteNode(root.left, key);}if(key > root.val){root.right = deleteNode(root.right, key);}return root;}
}

相关文章:

【LeetCode+JavaGuide打卡】Day22|235. 二叉搜索树的最近公共祖先、701.二叉搜索树中的插入操作、450.删除二叉搜索树中的节点

学习目标&#xff1a; 235. 二叉搜索树的最近公共祖先 701.二叉搜索树中的插入操作 450.删除二叉搜索树中的节点 学习内容&#xff1a; 235. 二叉搜索树的最近公共祖先 题目链接&&文章讲解 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最…...

Stable Diffusion WebUI 界面介绍

本文收录于《AI绘画从入门到精通》专栏,专栏总目录:点这里。 大家好,我是水滴~~ 本文主要对 Stable Diffusion WebUI 的界面进行简单的介绍,让你对该 WebUI 有个大致的了解,为后面的深入学习打下一个基础。主要内容包括:Stable Diffusion 模型(Stable Diffusion checkp…...

Cocos2dx-lua ScrollView[一]基础篇

一.ScrollView概述 cocos游戏中ScrollView控件大量使用,95%以上的项目都会使用ScrollView,个别游戏可能全部使用翻页的滑动效果。如果想要精通Cocos的UI开发,精通ScrollView控件非常关键,因此对ScrollView的使用进行总结很有必要。 下文缩写说明:sv = ScrollView, item代…...

QT应用软件【协议篇】周立功CAN接口卡代码示例

文章目录 USBCAN系列CAN接口卡规格参数资料下载QT引用周立功的库安装sdk代码USBCAN系列CAN接口卡 USBCAN系列CAN接口卡兼容USB2.0全速规范,可支持1/2/4/8路CAN接口。采用该接口卡,PC机可通过USB连入CAN网络,进行CAN总线数据采集和处理,主要具备以下几大优势特点: 支持车载…...

JVM对象的创建流程与内存分配

对象的创建流程与内存分配 创建流程对象内存分配方式内存分配安全问题对象内存分配流程【重要】:对象怎样才会进入老年代?重点 案例演示:对象分配过程大对象直接进入老年代02-对象内存分配的过程: 创建流程 加载 验证 解析 准备 初始化 使用 写在 对象内存分配方式 内存分配…...

docker (六)-进阶篇-数据持久化最佳实践MySQL部署

容器的数据挂载通常指的是将宿主机&#xff08;虚拟机或物理机&#xff09;上的目录或文件挂载到容器内部 MySQL单节点安装 详情参考docker官网文档 1 创建对应的数据目录、日志目录、配置文件目录(参考二进制安装&#xff0c;需自己建立数据存储目录) mkdir -p /data/mysq…...

力扣题目训练(17)

2024年2月10日力扣题目训练 2024年2月10日力扣题目训练551. 学生出勤记录 I557. 反转字符串中的单词 III559. N 叉树的最大深度241. 为运算表达式设计优先级260. 只出现一次的数字 III126. 单词接龙 II 2024年2月10日力扣题目训练 2024年2月10日第十七天编程训练&#xff0c;今…...

【react】react中和vue中的provide/inject、context写法示例

react写法 在 React 中&#xff0c;provide和inject的功能类似于 Vue.js 中的 provide和inject。它们都是用于跨组件层次传递数据的。 在 React 中&#xff0c;没有内置的 provide 和 inject 函数。但是&#xff0c;你可以使用 React 的 Context 来实现类似的功能。 Context…...

MySQL 的存储引擎(基本介绍)

文章目录 前言MySQL 的存储引擎介绍存储引擎是什么&#xff1f;存储引擎的特性? Innodb 与 Mylsam 的区别行级锁与表级锁是否支持事务是否支持恢复数据是否支持外键是否支持 MVCC 总结 前言 好文章不要错过&#xff0c;前两天跟大家分享的文章 1.MySQL的基础架构 2.SQL语句的…...

Unity3D 实现基于物理引擎的绳子关节解析详解

前言 在游戏开发中&#xff0c;有时候我们需要实现绳子关节效果&#xff0c;比如在射击游戏中射击绳子&#xff0c;或者在平衡游戏中使用绳子作为支撑。本文将详细介绍如何使用Unity3D的物理引擎实现绳子关节效果。 对惹&#xff0c;这里有一个游戏开发交流小组&#xff0c;希…...

C语言二级易忘易错易混知识点(自用)

1.数组名不能自加。 因为数组名实际上是一个指针&#xff0c;指向数组的第一个元素的地址。数组名在编译器中被视为常量&#xff0c;它的值是固定的&#xff0c;不能改变。 要访问数组的不同元素&#xff0c;应该使用数组名加上偏移量的方式来访问。 2.共用体只有最后一次赋值…...

js_三种方法实现深拷贝

深拷贝&#xff08; 递归 &#xff09; 适用于需要完全独立于原始对象的场景&#xff0c;特别是当对象内部有引用类型时&#xff0c;为了避免修改拷贝后的对象影响到原始对象&#xff0c;就需要使用深拷贝。 // 原始对象 const obj { uname: Lily,age: 19,hobby: [乒乓球, 篮球…...

【图论经典题目讲解】CF715B - Complete The Graph

C F 715 B − C o m p l e t e T h e G r a p h \mathrm{CF715B - Complete\ The\ Graph} CF715B−Complete The Graph D e s c r i p t i o n \mathrm{Description} Description 给定一张 n n n 个点&#xff0c; m m m 条边的无向图&#xff0c;点的编号为 0 ∼ n − 1 0\…...

[office] excel中数据汇总的大全教程文字版 #知识分享#经验分享#知识分享

excel中数据汇总的大全教程文字版 我们在excel中对数据清单上的数据进行分析的一种方法是分类汇总。在“数据”菜单上选择“分类汇总”命令&#xff0c;我们可以在数据清单中插入分类汇总行&#xff0c;然后按照选择的方式对数据进行汇总。同时&#xff0c;在插入分类汇总时&am…...

leetcode经典题库(简单)

文章目录 1.两数之和2.反转链表3.合并两个有序列表4.合并两个有序链表5.删除有序数组中的重复项6.从数组中移除元素7. 搜索指定数值在数组中的插入位置8. 数组最后一位加一9. 合并两个有序数组在leetcode上刷了几个和数组相关的简单题,记录在这里。 1.两数之和 给定一个整数…...

python coding with ChatGPT 打卡第21天| 二叉树:最近公共祖先

相关推荐 python coding with ChatGPT 打卡第12天| 二叉树&#xff1a;理论基础 python coding with ChatGPT 打卡第13天| 二叉树的深度优先遍历 python coding with ChatGPT 打卡第14天| 二叉树的广度优先遍历 python coding with ChatGPT 打卡第15天| 二叉树&#xff1a;翻转…...

openGauss学习笔记-224 openGauss性能调优-系统调优-数据库系统参数调优-数据库并发队列参数调优

文章目录 openGauss学习笔记-224 openGauss性能调优-系统调优-数据库系统参数调优-数据库并发队列参数调优224.1 全局并发队列224.2 局部并发队列 openGauss学习笔记-224 openGauss性能调优-系统调优-数据库系统参数调优-数据库并发队列参数调优 数据库提供两种手段进行并发队…...

UE5 C++ 创建可缩放的相机

一.要将相机设置在Pawn类里 1.在MyPawn头文件里&#xff0c;加上摇臂和相机组件 #include "GameFramework/SpringArmComponent.h" #include "Camera/CameraComponent.h" 2.在Pawm里声明SceneComponet&#xff0c;SpringArmComponent,CameraComponent组件…...

Fabric中的溯源方法

背景 在Fabric链码中&#xff0c;我们可以使用PutState方法对一个key的值进行覆盖&#xff0c;当我们再使用GetState查询时是最新的值。如果我们希望找到这个key的修改记录&#xff0c;我们可以使用溯源方法GetHistoryForKey。完整源码链接&#xff1a;https://github.com/hyp…...

混子文章|蓝桥杯一题 -平方差

题目考点: 平方差 ,平方差奇偶关系 代码 #include<bits/stdc.h> #define Run 0 #define endl "\n" #define N 100005 using unl __int128_t; using ll long long; using namespace std; class Solution { public: void slove() {int sum 0;int L, R; cin &…...

SpringBoot-17-MyBatis动态SQL标签之常用标签

文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...

日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻

在如今就业市场竞争日益激烈的背景下&#xff0c;越来越多的求职者将目光投向了日本及中日双语岗位。但是&#xff0c;一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧&#xff1f;面对生疏的日语交流环境&#xff0c;即便提前恶补了…...

synchronized 学习

学习源&#xff1a; https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖&#xff0c;也要考虑性能问题&#xff08;场景&#xff09; 2.常见面试问题&#xff1a; sync出…...

CTF show Web 红包题第六弹

提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框&#xff0c;很难让人不联想到SQL注入&#xff0c;但提示都说了不是SQL注入&#xff0c;所以就不往这方面想了 ​ 先查看一下网页源码&#xff0c;发现一段JavaScript代码&#xff0c;有一个关键类ctfs…...

大话软工笔记—需求分析概述

需求分析&#xff0c;就是要对需求调研收集到的资料信息逐个地进行拆分、研究&#xff0c;从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要&#xff0c;后续设计的依据主要来自于需求分析的成果&#xff0c;包括: 项目的目的…...

基于Flask实现的医疗保险欺诈识别监测模型

基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施&#xff0c;由雇主和个人按一定比例缴纳保险费&#xff0c;建立社会医疗保险基金&#xff0c;支付雇员医疗费用的一种医疗保险制度&#xff0c; 它是促进社会文明和进步的…...

MVC 数据库

MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...

对WWDC 2025 Keynote 内容的预测

借助我们以往对苹果公司发展路径的深入研究经验&#xff0c;以及大语言模型的分析能力&#xff0c;我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际&#xff0c;我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测&#xff0c;聊作存档。等到明…...

解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错

出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上&#xff0c;所以报错&#xff0c;到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本&#xff0c;cu、torch、cp 的版本一定要对…...

成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战

在现代战争中&#xff0c;电磁频谱已成为继陆、海、空、天之后的 “第五维战场”&#xff0c;雷达作为电磁频谱领域的关键装备&#xff0c;其干扰与抗干扰能力的较量&#xff0c;直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器&#xff0c;凭借数字射…...