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

day21-二叉树part08

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

        相对于 二叉树的最近公共祖先 本题就简单一些了,因为 可以利用二叉搜索树的特性无需全部遍历。特点:当前节点在p,q节点之前则必为最近公共祖先

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root == null){return root;}//当前节点大于p,q节点值往当前节点左子树遍历if(root.val > p.val && root.val > q.val){TreeNode left = lowestCommonAncestor(root.left,p,q);if(left != null){return left;}}//当前节点小于p,q节点值往当前节点右子树遍历if(root.val < q.val && root.val < p.val){TreeNode right = lowestCommonAncestor(root.right,p,q);if(right != null){return right;}}//如果当前节点值在两个节点值中间这就是最近公共祖先if(root.val > p.val && root.val < q.val){return root;}return root;}
}

迭代法:

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {while(root != null){//p,q节点都在左if(root.val > p.val && root.val > q.val){root = root.left;//p,q节点都在右}else if(root.val < q.val && root.val < p.val){root = root.right;//当前节点在p,q中间}else{return root;}}return root;}
}

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

思路:只需要在叶子节点上可以找到我们要插入的新节点位置,向上放回新节点给上一个节点进行操作

通过递归函数返回值完成了新加入节点的父子关系赋值操作了,下一层将加入节点返回,本层用root->left或者root->right将其接住

class Solution {public TreeNode insertIntoBST(TreeNode root, int val) {//递归终止条件 递归到叶子节点 创建新节点返回给上一个节点if(root == null){return new TreeNode(val);}//当前节点值大于val 将新节点插入当前节点的左侧if(root.val > val){root.left = insertIntoBST(root.left,val);}if(root.val < val){root.right = insertIntoBST(root.right,val);}return root;}
}

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

        五种情况

        1.没找到删除节点,遍历到空节点直接返回

        2.遍历到删除节点,删除节点左右子树为空,向上返回null

        3.遍历到删除节点,删除节点左子树为空右子树不为空 返回右子树节点

        4.遍历到删除节点,删除节点左子树不为空右子树为空  返回左子树节点

        5.遍历到删除节点,删除节点左右子树都不为空 将删除节点左子树头节点放到删除节点右子树下最左面节点的左孩子上,返回删除节点右孩子为新的根节点

class Solution {public TreeNode deleteNode(TreeNode root, int key) {//终止条件找到删除节点 执行删除节点逻辑 将删除完的操作节点返回给上一个节点//没有找到删除节点if(root == null){return root;}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;}//再将删除节点的左子树连接到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;}
}

相关文章:

day21-二叉树part08

235. 二叉搜索树的最近公共祖先 相对于 二叉树的最近公共祖先 本题就简单一些了&#xff0c;因为 可以利用二叉搜索树的特性无需全部遍历。特点&#xff1a;当前节点在p&#xff0c;q节点之前则必为最近公共祖先 class Solution {public TreeNode lowestCommonAncestor(TreeNo…...

【WPF应用42】WPF中的 GroupBox 控件详解

在 Windows Presentation Foundation (WPF) 中&#xff0c;控件是构建用户界面 (UI) 的基础。WPF 提供了丰富的控件库&#xff0c;其中包括 GroupBox 控件&#xff0c;它用于将相关的 UI 元素组织到逻辑分组中。在本博客文章中&#xff0c;我们将详细介绍 GroupBox 控件的功能、…...

LeetCode-72. 编辑距离【字符串 动态规划】

LeetCode-72. 编辑距离【字符串 动态规划】 题目描述&#xff1a;解题思路一&#xff1a;动规五部曲解题思路二&#xff1a;动态规划【版本二】解题思路三&#xff1a;0 题目描述&#xff1a; 给你两个单词 word1 和 word2&#xff0c; 请返回将 word1 转换成 word2 所使用的最…...

多张静图合成gif怎么做?一键极速合成gif

图片的格式有很多种&#xff0c;通常分为静态图片和动态图片。而动态图片基本上都是gif格式&#xff0c;想要把其他格式的静图变成gif格式动图的时候要怎么操作呢&#xff1f;通过使用gif动画图片&#xff08;https://www.gif.cn/&#xff09;制作网站&#xff0c;上传jpg、png…...

Es中bool 查询中的四个(must must_not should filter)

1.must :相当于and 2.must_not :相当于not 3.should:相当于or 4. filter:过滤 gte 大于 gt大于 lte小于等于 lt小于 使用示例&#xff1a; {“bool”:{“must”:{“match”:{“title”:”how to make millons “}},“must_not”:{“match”:{“tag”:”spam“}},“should”:[{…...

Docker容器嵌入式开发:Docker Ubuntu18.04配置mysql数据库

在 Ubuntu 18.04 操作系统中安装 MySQL 数据库的过程。下面是安装过程的详细描述&#xff1a; 首先&#xff0c;使用以下命令安装 MySQL 服务器&#xff1a; sudo apt install mysql-server系统会提示是否继续安装&#xff0c;按下 Y 键确认。 安装过程中&#xff0c;系统会…...

C++类和对象中上篇

1.类的6个默认成员函数 如果一个类中什么成员都没有&#xff0c;那就简称他为空类。 空类中真的什么都没有吗&#xff1f;并不是&#xff0c;任何类在什么都不写时&#xff0c;编译器会自动生成以下6个默认成员函数。 默认成员函数&#xff1a;用户没有显式实现&#xff0c;…...

基于linux进一步理解核间通讯

芯片架构分为同构和异构: 如下图TC397: 如下图TDA4: 如下图STM32MP157: 非对称多处理结构(AMP): AMP 结构是指每个内核运行自己的 OS 或同一 OS 的独立实例&#...

应用实战|从头开始开发记账本2:基于模板快速开始

上期视频我们创建好了BaaS服务的后端应用。从这期视频开始&#xff0c;我们将从头开发一个互联网记账本应用。本期视频我们介绍一下如何使用模板快速开启我们的应用开发之旅。 应用实战&#xff5c;从头开始开发记账本2&#xff1a;基于模板快速开始 相关代码 本期视频我们介绍…...

学习前端第二十天(条件分支:if 和 ‘?‘;逻辑运算符)

一、条件分支 if (…) 语句会计算圆括号内的表达式&#xff0c;并将计算结果转换为布尔型。 if(...) 语句计算括号里的条件表达式&#xff0c;如果计算结果是 true&#xff0c;就会执行对应的代码块{ }。 if 语句有时会包含一个可选的 “else” 块。如果判断条件不成立&…...

C++11的更新介绍(lamada、包装器)

&#x1fa90;&#x1fa90;&#x1fa90;欢迎来到程序员餐厅&#x1f4ab;&#x1f4ab;&#x1f4ab; 主厨&#xff1a;邪王真眼 主厨的主页&#xff1a;Chef‘s blog 所属专栏&#xff1a;c大冒险 总有光环在陨落&#xff0c;总有新星在闪烁 lambda表达式 C98中的一个…...

Golang 实现一个简单的 RPC 服务

分享一个简单的 rpc 服务框架 一、服务端实现 package mainimport ("log""net""net/rpc" )const HelloServiceName "main.HelloService"type HelloServiceInterface interface {Hello(request string, replay *string) error }func…...

Linux系统(centos,redhat,龙芯,麒麟等)忘记密码,怎么设置新的密码

Linux系统&#xff08;centos,redhat,龙芯&#xff0c;麒麟等&#xff09;忘记密码&#xff0c;怎么设置新的密码 今天在操作服务器时&#xff0c;DBA忘记了人大金仓数据库的kingbase密码&#xff0c;他的密码试了好多遍&#xff0c;都不行。最后只能给重置密码了 解决办法&a…...

SpringBoot的启动原理

运行Main方法&#xff1a; 应用程序启动始于Main方法的执行。在Main方法中&#xff0c;创建了一个SpringApplication实例&#xff0c;用于引导应用程序的启动。同时&#xff0c;SpringApplication会根据spring.factories文件加载并注册监听器、ApplicationContextInitializer等…...

git查看单独某一个文件的历史修改记录

git查看单独某一个文件的历史修改记录 git log -p 文件具体路径 注意&#xff0c;Windows下默认文件路径分隔符是 \&#xff0c;在git bash 里面需要改成 /。 git基于change代码修改与提交_git change-CSDN博客文章浏览阅读361次。git cherry-pick&#xff1a;复制多个提交comm…...

一键开启Scrum回顾会议的精彩时刻

其实回顾会议作为一个检视、反馈、改进环节&#xff0c;不仅在传统的瀑布管理模式中&#xff0c;还是在Scrum一类的敏捷管理流程中&#xff0c;都是非常重要的活动。一些团队认为它无法产生直接的价值&#xff0c;所以有意忽略了这个会议&#xff1b;一些团队在越来越多的回顾中…...

Python计算多个表格中多列数据的平均值与标准差并导出为新的Excel文件

本文介绍基于Python语言&#xff0c;对一个或多个表格文件中多列数据分别计算平均值与标准差&#xff0c;随后将多列数据对应的这2个数据结果导出为新的表格文件的方法。 首先&#xff0c;来看一下本文的需求。现有2个.csv格式的表格文件&#xff0c;其每1列表示1个变量&#x…...

nginx支持的多种负载均衡策略

目录 1.轮询&#xff08;默认&#xff09; 2. ip_hash 3. 加权轮询&#xff08;weight&#xff09; 4. fair&#xff08;第三方&#xff09; 5. 最少连接&#xff08;least_conn&#xff09; 1.轮询&#xff08;默认&#xff09; 将请求依次分配给每个服务器&#xff0c;确…...

FNP preptool has not been run on this executable

pycharm导入arcgis pro的python运行程序后提示 我也看了很多解决方法&#xff0c;也重新安装过一遍&#xff0c;终于看到一个说法是你的arcgis pro是学习版所以才会有这个提示&#xff0c;不会影响输入 测试代码 import arcpy print(arcpy.GetInstallInfo()[Version])输出结果…...

算法-反转单向链表

需求 思路 链表必有节点&#xff0c;节点两要素&#xff1a;当前元素值&#xff0c;下一个节点地址 import java.util.Scanner;// 定义一个单向链表 public class MyLinkedList<E> {int size 0;// 顶一个私有的内部类&#xff0c;表示链表的节点public class Node {E da…...

汽车生产虚拟实训中的技能提升与生产优化​

在制造业蓬勃发展的大背景下&#xff0c;虚拟教学实训宛如一颗璀璨的新星&#xff0c;正发挥着不可或缺且日益凸显的关键作用&#xff0c;源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例&#xff0c;汽车生产线上各类…...

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例

文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...

【数据分析】R版IntelliGenes用于生物标志物发现的可解释机器学习

禁止商业或二改转载&#xff0c;仅供自学使用&#xff0c;侵权必究&#xff0c;如需截取部分内容请后台联系作者! 文章目录 介绍流程步骤1. 输入数据2. 特征选择3. 模型训练4. I-Genes 评分计算5. 输出结果 IntelliGenesR 安装包1. 特征选择2. 模型训练和评估3. I-Genes 评分计…...

Java 二维码

Java 二维码 **技术&#xff1a;**谷歌 ZXing 实现 首先添加依赖 <!-- 二维码依赖 --><dependency><groupId>com.google.zxing</groupId><artifactId>core</artifactId><version>3.5.1</version></dependency><de…...

【Java学习笔记】BigInteger 和 BigDecimal 类

BigInteger 和 BigDecimal 类 二者共有的常见方法 方法功能add加subtract减multiply乘divide除 注意点&#xff1a;传参类型必须是类对象 一、BigInteger 1. 作用&#xff1a;适合保存比较大的整型数 2. 使用说明 创建BigInteger对象 传入字符串 3. 代码示例 import j…...

Python ROS2【机器人中间件框架】 简介

销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...

Chrome 浏览器前端与客户端双向通信实战

Chrome 前端&#xff08;即页面 JS / Web UI&#xff09;与客户端&#xff08;C 后端&#xff09;的交互机制&#xff0c;是 Chromium 架构中非常核心的一环。下面我将按常见场景&#xff0c;从通道、流程、技术栈几个角度做一套完整的分析&#xff0c;特别适合你这种在分析和改…...

嵌入式常见 CPU 架构

架构类型架构厂商芯片厂商典型芯片特点与应用场景PICRISC (8/16 位)MicrochipMicrochipPIC16F877A、PIC18F4550简化指令集&#xff0c;单周期执行&#xff1b;低功耗、CIP 独立外设&#xff1b;用于家电、小电机控制、安防面板等嵌入式场景8051CISC (8 位)Intel&#xff08;原始…...

rm视觉学习1-自瞄部分

首先先感谢中南大学的开源&#xff0c;提供了很全面的思路&#xff0c;减少了很多基础性的开发研究 我看的阅读的是中南大学FYT战队开源视觉代码 链接&#xff1a;https://github.com/CSU-FYT-Vision/FYT2024_vision.git 1.框架&#xff1a; 代码框架结构&#xff1a;readme有…...

用神经网络读懂你的“心情”:揭秘情绪识别系统背后的AI魔法

用神经网络读懂你的“心情”:揭秘情绪识别系统背后的AI魔法 大家好,我是Echo_Wish。最近刷短视频、看直播,有没有发现,越来越多的应用都开始“懂你”了——它们能感知你的情绪,推荐更合适的内容,甚至帮客服识别用户情绪,提升服务体验。这背后,神经网络在悄悄发力,撑起…...