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

力扣刷题TOP101: 31.BM38 在二叉树中找到两个节点的最近公共祖先

目录:

目的

思路

复杂度

记忆秘诀

python代码

目的:

给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的val值 o1 和 o2,请找o1 和 o2 的最近公共祖先节点。


思路

这个任务目和上一题在二叉搜索树中找到两个节点的最近公共祖先有点类似,都是找最近公共祖先。但是区别在于一个有序一个无序。

力扣刷题TOP101: 30.BM37 二叉搜索树的最近公共祖先-CSDN博客 

特点普通二叉树二叉搜索树
数据结构特性无排序特性,任意结构左小右大,具有排序特
算法实现深度优先搜索(DFS),逐层递归利用节点值,逐层比较,不需要完整遍历
时间复杂度O(n),需要访问所有节点O(h),只需沿着路径查找
适用范围任意二叉树仅适用于二叉搜索树
效率较低较高

代码逻辑:

  • 如果当前节点为空

    • 说明这里没有要找的两个节点,直接返回 -1 表示没有找到。
  • 如果当前节点就是其中一个目标节点

    • 说明当前节点可能是最近公共祖先(或者它是两个节点之一),直接返回当前节点的值。
  • 递归查找左右子树

    • 递归地查找左子树,看是否能找到目标节点之一。如果找到了,返回对应的值;如果没找到,返回 -1
    • 递归地查找右子树,看是否能找到目标节点之一。如果找到了,返回对应的值;如果没找到,返回 -1
  • 根据左右子树的结果判断

    • 如果左子树没找到(返回 -1),说明两个节点都在右子树,直接返回右子树的结果。
    • 如果右子树没找到(返回 -1),说明两个节点都在左子树,直接返回左子树的结果。
    • 如果左右子树都找到了目标节点,说明当前节点是它们的最近公共祖先,直接返回当前节点的值。

示例:假设有以下二叉树,目标是找到节点 45 的最近公共祖先

        1/ \2   3/ \4   5

递归过程:

  • 从根节点 1 开始

    • 左子树递归:去节点 2 中查找。
    • 右子树递归:去节点 3 中查找。
  • 节点 2 的子树

    • 左子树递归:在节点 4 找到目标节点 4
    • 右子树递归:在节点 5 找到目标节点 5
    • 左右子树都找到目标,返回节点 2 作为最近公共祖先。
  • 节点 3 的子树

    • 左右子树递归:都为空,返回 -1
  • 回到根节点 1

    • 左子树返回节点 2。
    • 右子树返回 -1
    • 因为只有左子树找到目标,最终结果是节点 2

复杂度

  • 时间复杂度:O(n)

    • 这是一个典型的 深度优先搜索(DFS),每个节点在递归过程中最多会被访问一次。
  • 空间复杂度:O(h)

    • 最坏情况下(链表形式的树):O(h), 其中 h 是树的高度。
    • 最佳情况下(完全平衡的树):O(log⁡h)。

记忆秘诀

  • 子树为空,返回无结果
  • 当前节点是目标节点,返回自己
  • 递归查找左右子树

    • 两边都找到,当前节点是答案;

    • 只找到一边,继续返回那边结果


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 一直没仔细看过,其实有包含鼠标相关的很多参数,鼠标点击次数&#xff…...

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 框架

技术博客&#xff1a;探索 Robyn 框架 —— 下一代高性能 Web 框架 什么是 Robyn&#xff1f; Robyn 是一个用 Rust 编写的高性能 Web 框架&#xff0c;旨在通过极简设计和高效并发处理&#xff0c;帮助开发者快速构建可扩展的现代 Web 应用。得益于 Rust 的内存安全性和性能…...

Spring Boot 实现流式响应(兼容 2.7.x)

在实际开发中&#xff0c;我们可能会遇到一些流式数据处理的场景&#xff0c;比如接收来自上游接口的 Server-Sent Events&#xff08;SSE&#xff09; 或 流式 JSON 内容&#xff0c;并将其原样中转给前端页面或客户端。这种情况下&#xff0c;传统的 RestTemplate 缓存机制会…...

.Net框架,除了EF还有很多很多......

文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...

MMaDA: Multimodal Large Diffusion Language Models

CODE &#xff1a; https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA&#xff0c;它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构&#xf…...

RSS 2025|从说明书学习复杂机器人操作任务:NUS邵林团队提出全新机器人装配技能学习框架Manual2Skill

视觉语言模型&#xff08;Vision-Language Models, VLMs&#xff09;&#xff0c;为真实环境中的机器人操作任务提供了极具潜力的解决方案。 尽管 VLMs 取得了显著进展&#xff0c;机器人仍难以胜任复杂的长时程任务&#xff08;如家具装配&#xff09;&#xff0c;主要受限于人…...

为什么要创建 Vue 实例

核心原因:Vue 需要一个「控制中心」来驱动整个应用 你可以把 Vue 实例想象成你应用的**「大脑」或「引擎」。它负责协调模板、数据、逻辑和行为,将它们变成一个活的、可交互的应用**。没有这个实例,你的代码只是一堆静态的 HTML、JavaScript 变量和函数,无法「活」起来。 …...

上位机开发过程中的设计模式体会(1):工厂方法模式、单例模式和生成器模式

简介 在我的 QT/C 开发工作中&#xff0c;合理运用设计模式极大地提高了代码的可维护性和可扩展性。本文将分享我在实际项目中应用的三种创造型模式&#xff1a;工厂方法模式、单例模式和生成器模式。 1. 工厂模式 (Factory Pattern) 应用场景 在我的 QT 项目中曾经有一个需…...

前端工具库lodash与lodash-es区别详解

lodash 和 lodash-es 是同一工具库的两个不同版本&#xff0c;核心功能完全一致&#xff0c;主要区别在于模块化格式和优化方式&#xff0c;适合不同的开发环境。以下是详细对比&#xff1a; 1. 模块化格式 lodash 使用 CommonJS 模块格式&#xff08;require/module.exports&a…...

Java中HashMap底层原理深度解析:从数据结构到红黑树优化

一、HashMap概述与核心特性 HashMap作为Java集合框架中最常用的数据结构之一&#xff0c;是基于哈希表的Map接口非同步实现。它允许使用null键和null值&#xff08;但只能有一个null键&#xff09;&#xff0c;并且不保证映射顺序的恒久不变。与Hashtable相比&#xff0c;Hash…...

C++11 constexpr和字面类型:从入门到精通

文章目录 引言一、constexpr的基本概念与使用1.1 constexpr的定义与作用1.2 constexpr变量1.3 constexpr函数1.4 constexpr在类构造函数中的应用1.5 constexpr的优势 二、字面类型的基本概念与使用2.1 字面类型的定义与作用2.2 字面类型的应用场景2.2.1 常量定义2.2.2 模板参数…...

Spring事务传播机制有哪些?

导语&#xff1a; Spring事务传播机制是后端面试中的必考知识点&#xff0c;特别容易出现在“项目细节挖掘”阶段。面试官通过它来判断你是否真正理解事务控制的本质与异常传播机制。本文将从实战与源码角度出发&#xff0c;全面剖析Spring事务传播机制&#xff0c;帮助你答得有…...