力扣刷题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 的内存安全性和性能…...
椭圆曲线密码学(ECC)
一、ECC算法概述 椭圆曲线密码学(Elliptic Curve Cryptography)是基于椭圆曲线数学理论的公钥密码系统,由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA,ECC在相同安全强度下密钥更短(256位ECC ≈ 3072位RSA…...
电脑插入多块移动硬盘后经常出现卡顿和蓝屏
当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时,可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案: 1. 检查电源供电问题 问题原因:多块移动硬盘同时运行可能导致USB接口供电不足&#x…...
HTML前端开发:JavaScript 常用事件详解
作为前端开发的核心,JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例: 1. onclick - 点击事件 当元素被单击时触发(左键点击) button.onclick function() {alert("按钮被点击了!&…...
Java面试专项一-准备篇
一、企业简历筛选规则 一般企业的简历筛选流程:首先由HR先筛选一部分简历后,在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如:Boss直聘(招聘方平台) 直接按照条件进行筛选 例如:…...
AspectJ 在 Android 中的完整使用指南
一、环境配置(Gradle 7.0 适配) 1. 项目级 build.gradle // 注意:沪江插件已停更,推荐官方兼容方案 buildscript {dependencies {classpath org.aspectj:aspectjtools:1.9.9.1 // AspectJ 工具} } 2. 模块级 build.gradle plu…...
《C++ 模板》
目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板,就像一个模具,里面可以将不同类型的材料做成一个形状,其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式:templa…...
RSS 2025|从说明书学习复杂机器人操作任务:NUS邵林团队提出全新机器人装配技能学习框架Manual2Skill
视觉语言模型(Vision-Language Models, VLMs),为真实环境中的机器人操作任务提供了极具潜力的解决方案。 尽管 VLMs 取得了显著进展,机器人仍难以胜任复杂的长时程任务(如家具装配),主要受限于人…...
Caliper 配置文件解析:fisco-bcos.json
config.yaml 文件 config.yaml 是 Caliper 的主配置文件,通常包含以下内容: test:name: fisco-bcos-test # 测试名称description: Performance test of FISCO-BCOS # 测试描述workers:type: local # 工作进程类型number: 5 # 工作进程数量monitor:type: - docker- pro…...
第八部分:阶段项目 6:构建 React 前端应用
现在,是时候将你学到的 React 基础知识付诸实践,构建一个简单的前端应用来模拟与后端 API 的交互了。在这个阶段,你可以先使用模拟数据,或者如果你的后端 API(阶段项目 5)已经搭建好,可以直接连…...
Django RBAC项目后端实战 - 03 DRF权限控制实现
项目背景 在上一篇文章中,我们完成了JWT认证系统的集成。本篇文章将实现基于Redis的RBAC权限控制系统,为系统提供细粒度的权限控制。 开发目标 实现基于Redis的权限缓存机制开发DRF权限控制类实现权限管理API配置权限白名单 前置配置 在开始开发权限…...
