力扣刷题TOP101: 31.BM38 在二叉树中找到两个节点的最近公共祖先
目录:
目的
思路
复杂度
记忆秘诀
python代码
目的:
给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的val值 o1 和 o2,请找o1 和 o2 的最近公共祖先节点。
思路
这个任务目和上一题在二叉搜索树中找到两个节点的最近公共祖先有点类似,都是找最近公共祖先。但是区别在于一个有序一个无序。
力扣刷题TOP101: 30.BM37 二叉搜索树的最近公共祖先-CSDN博客
| 特点 | 普通二叉树 | 二叉搜索树 |
|---|---|---|
| 数据结构特性 | 无排序特性,任意结构 | 左小右大,具有排序特性 |
| 算法实现 | 深度优先搜索(DFS),逐层递归 | 利用节点值,逐层比较,不需要完整遍历 |
| 时间复杂度 | O(n),需要访问所有节点 | O(h),只需沿着路径查找 |
| 适用范围 | 任意二叉树 | 仅适用于二叉搜索树 |
| 效率 | 较低 | 较高 |
代码逻辑:
如果当前节点为空
- 说明这里没有要找的两个节点,直接返回
-1表示没有找到。如果当前节点就是其中一个目标节点
- 说明当前节点可能是最近公共祖先(或者它是两个节点之一),直接返回当前节点的值。
递归查找左右子树
- 递归地查找左子树,看是否能找到目标节点之一。如果找到了,返回对应的值;如果没找到,返回
-1。- 递归地查找右子树,看是否能找到目标节点之一。如果找到了,返回对应的值;如果没找到,返回
-1。根据左右子树的结果判断
- 如果左子树没找到(返回
-1),说明两个节点都在右子树,直接返回右子树的结果。- 如果右子树没找到(返回
-1),说明两个节点都在左子树,直接返回左子树的结果。- 如果左右子树都找到了目标节点,说明当前节点是它们的最近公共祖先,直接返回当前节点的值。
示例:假设有以下二叉树,目标是找到节点 4 和 5 的最近公共祖先:
1/ \2 3/ \4 5
递归过程:
-
从根节点 1 开始:
- 左子树递归:去节点 2 中查找。
- 右子树递归:去节点 3 中查找。
-
节点 2 的子树:
- 左子树递归:在节点 4 找到目标节点
4。 - 右子树递归:在节点 5 找到目标节点
5。 - 左右子树都找到目标,返回节点 2 作为最近公共祖先。
- 左子树递归:在节点 4 找到目标节点
-
节点 3 的子树:
- 左右子树递归:都为空,返回
-1。
- 左右子树递归:都为空,返回
-
回到根节点 1:
- 左子树返回节点 2。
- 右子树返回
-1。 - 因为只有左子树找到目标,最终结果是节点 2。
复杂度
-
时间复杂度:O(n)
- 这是一个典型的 深度优先搜索(DFS),每个节点在递归过程中最多会被访问一次。
-
空间复杂度:O(h)
- 最坏情况下(链表形式的树):O(h), 其中 h 是树的高度。
- 最佳情况下(完全平衡的树):O(logh)。
记忆秘诀
- 子树为空,返回无结果
- 当前节点是目标节点,返回自己
递归查找左右子树:
两边都找到,当前节点是答案;
只找到一边,继续返回那边结果。
python代码
class TreeNode:def __init__(self, x):self.val = xself.left = Noneself.right = Noneclass Solution:def lowestCommonAncestor(self , root: TreeNode, o1: int, o2: int) -> int:# 该子树没找到,返回-1if not root:return -1# 该节点是其中某一个节点if root.val == o1 or root.val == o2:return root.val# 左子树寻找公共祖先left = self.lowestCommonAncestor(root.left, o1, o2)# 右子树寻找公共祖先right = self.lowestCommonAncestor(root.right, o1, o2)# 左子树为没找到,则在右子树中if left == -1:return right# 右子树没找到,则在左子树中if right == -1:return left# 否则是当前节点return root.val
* 欢迎大家探讨新思路,能够更好的理解和记忆
相关文章:
力扣刷题TOP101: 31.BM38 在二叉树中找到两个节点的最近公共祖先
目录: 目的 思路 复杂度 记忆秘诀 python代码 目的: 给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的val值 o1 和 o2,请找o1 和 o2 的最近公共祖先节点。 思路 这个任务目和上一题在二叉搜索树中找到两个节点的最近公共祖先有点类…...
前端项目打包部署
打包和部署前端项目是将开发环境中的代码转化为生产环境可直接运行的静态文件,并将其部署到服务器上的过程。 # 项目打包 pnpm run build# 上传文件至远程服务器 将本地打包生成的 dist 目录下的所有文件拷贝至服务器的 /usr/share/nginx/html 目录。# nginx.cofig…...
《CSS 知识点》大屏卡片布局思路:弹性布局 flex-grow
思路 大屏左右两侧高宽一致,内部卡片可按比例设置! 使用弹性布局和属性 flex-grow 设置比例;间隔使用 margin-bottom 设置,最后一个卡片不设置; 效果如图 代码说明 CSS代码 26 - 30,左右两侧设置弹性布…...
nVisual 登录页页面配置说明
一、概述 nVisual登录页面可根据具体客户需要通过public\config\access.js文件进行自定义配置。页面可以大致分为4个部分,头部、底部、可移动区域以及页面中间的信息填写区域。其中头部和底部又包含头部左侧、头部中间、头部右侧、底部左侧、底部中间、底部右侧六个…...
后端接受前端传递数组进行批量删除
问题描述:当我们需要做批量删除功能的时候,我们循环单次删除的接口也能进行批量删除,但要删除100条数据就要调用100次接口,或者执行100次sql,这样系统开销是比较大的,那么我们直接采用接收的数组格式数据sq…...
拍频实例 - 一组恒力矩电流采样数据
这是一组功率电机的感应电流波形。加载了重载恒力矩设备。你能看到什么? 首先,时间轴的坐标是对的,9.9~10.0秒,单位是秒,100ms有5个波形,所以是20ms一个波形。这是50Hz的信号。频差就体现为幅度的周期起伏…...
Jvm之NativeMemoryTracking 使用
开启 Native Memory Tracking 通过 -XX:NativeMemoryTracking 开启: -XX:NativeMemoryTrackingoff:这是默认值,即关闭 Native Memory Tracking -XX:NativeMemoryTrackingsummary: 开启 Native Memory Tracking,但是仅仅按照各个 JVM 子系统…...
PKCS#7、Bit padding(位填充)、Byte padding(字节填充)、Zero padding(零填充)
PKCS#7、Bit padding(位填充)、Byte padding(字节填充)、Zero padding(零填充)是密码学常见的填充方式。 Bit padding(位填充): 位填充可以应用于任意长度的消息。在消息…...
R语言学习笔记-1
1. 基础操作和函数 清空环境:rm(list ls()) 用于清空当前的R环境。 打印输出:print("Hello, world") 用于输出文本到控制台。 查看已安装包和加载包: search():查看当前加载的包。install.packages("package_na…...
我在广州学 Mysql 系列之 数据“表”的基本操作
ℹ️大家好,我是😆练小杰,今天主要讲得是Mysql数据表的基本操作内容~~ 昨天讲了“Mysql 数据“库“的基本操作”~~ 想要了解更多🈶️MYSQL 数据库的命令行总结!!! “真相永远只有一个”——工藤…...
auto-gptq安装以及不适配软硬件环境可能出现的问题及解决方式
目录 1、auto-gptq是什么?2、auto-gptq安装3、auto-gptq不正确安装可能会出现的问题(1)爆出:CUDA extension not installed.(2)没有报错但是推理速度超级慢 1、auto-gptq是什么? Auto-GPTQ 是一…...
【R语言】基础知识
一、对象与变量 R语言中的所有事物都是对象,如向量、列表、函数,变量、甚至环境等。它的所有代码都是基于对象object的操作,变量只是调用对象的手段。 1、对象 在R语言中,对计算机内存的访问是通过对象实现的。 # 字符型向量 …...
【一本通】虫洞
【一本通】虫洞 C语言代码C代码JAVA代码 💐The Begin💐点点关注,收藏不迷路💐 John在他的农场中闲逛时发现了许多虫洞。虫洞可以看作一条十分奇特的有向边,并可以使你返回到过去的一个时刻(相对你进入虫洞之…...
python爬虫--小白篇【爬虫实践】
一、前言 1.1、王者荣耀皮肤爬虫 根据王者荣耀链接,将王者荣耀的全部英雄的全部皮肤图片爬取保存到本地。经过分析得到任务的三个步骤: 根据首页全部英雄列表连接获取全部英雄的名称hero_name以及对应的hero_id;根据单个英雄的hero_name和h…...
Unity背包道具拖拽(极简版实现)
(感觉Csdn代码页面可以再大一点或者加个放大功能 不然得划着看不太舒服) 1.关键接口,三个拖拽相关的 2.关键参数,PointerEventData 一直没仔细看过,其实有包含鼠标相关的很多参数,鼠标点击次数ÿ…...
spark读取普通文件
spark读取普通文件 txt文件 """ 将一行数据当做一个字段,需要自己切割 字段名称为value 表结构 可以从sql中搞 """ df spark.read.text("../../data/wordcount/input/data.txt") df spark.read.format("text"…...
MySQL SQL语句性能优化
MySQL SQL语句性能优化指南 一、查询设计优化1. 避免 SELECT *2. 使用 WHERE 进行条件过滤3. 避免在索引列上使用函数和表达式4. 使用 LIMIT 限制返回行数5. 避免使用子查询6. 优化 JOIN 操作7. 避免全表扫描 二、索引优化1. 使用合适的索引2. 覆盖索引3. 索引选择性4. 多列索引…...
【蓝桥杯每日一题】技能升级
技能升级 2024-12-10 蓝桥杯每日一题 技能升级 二分 题目大意 一个角色有 N 种可以增加攻击力的技能,对于第 i 个技能首次升级可以提升 A i A_i Ai 点攻击力,随后的每次升级增加的攻击力都会减少 B i B_i Bi 。升级 ⌈ A i B i ⌉ \lceil \frac{A…...
css 实现在一条线上流动小物体(offset-path)
直接贴代码,留几个参考网址给大家 【SVG】路径<Path>标签详解,一次搞懂所有命令参数 探秘神奇的运动路径动画 Motion Path <!DOCTYPE html> <html lang="en"> <head><meta charset="UTF-8"><meta name="viewport&quo…...
探索 Robyn 框架 —— 下一代高性能 Web 框架
技术博客:探索 Robyn 框架 —— 下一代高性能 Web 框架 什么是 Robyn? Robyn 是一个用 Rust 编写的高性能 Web 框架,旨在通过极简设计和高效并发处理,帮助开发者快速构建可扩展的现代 Web 应用。得益于 Rust 的内存安全性和性能…...
微信小程序之bind和catch
这两个呢,都是绑定事件用的,具体使用有些小区别。 官方文档: 事件冒泡处理不同 bind:绑定的事件会向上冒泡,即触发当前组件的事件后,还会继续触发父组件的相同事件。例如,有一个子视图绑定了b…...
前端倒计时误差!
提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...
(二)TensorRT-LLM | 模型导出(v0.20.0rc3)
0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述,后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作,其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...
高等数学(下)题型笔记(八)空间解析几何与向量代数
目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...
Python爬虫(一):爬虫伪装
一、网站防爬机制概述 在当今互联网环境中,具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类: 身份验证机制:直接将未经授权的爬虫阻挡在外反爬技术体系:通过各种技术手段增加爬虫获取数据的难度…...
12.找到字符串中所有字母异位词
🧠 题目解析 题目描述: 给定两个字符串 s 和 p,找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义: 若两个字符串包含的字符种类和出现次数完全相同,顺序无所谓,则互为…...
C# SqlSugar:依赖注入与仓储模式实践
C# SqlSugar:依赖注入与仓储模式实践 在 C# 的应用开发中,数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护,许多开发者会选择成熟的 ORM(对象关系映射)框架,SqlSugar 就是其中备受…...
项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)
Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败,具体原因是客户端发送了密码认证请求,但Redis服务器未设置密码 1.为Redis设置密码(匹配客户端配置) 步骤: 1).修…...
初学 pytest 记录
安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...
安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖
在Vuzix M400 AR智能眼镜的助力下,卢森堡罗伯特舒曼医院(the Robert Schuman Hospitals, HRS)凭借在无菌制剂生产流程中引入增强现实技术(AR)创新项目,荣获了2024年6月7日由卢森堡医院药剂师协会࿰…...
