当前位置: 首页 > 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 的内存安全性和性能…...

在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:

在 HarmonyOS 应用开发中&#xff0c;手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力&#xff0c;既支持点击、长按、拖拽等基础单一手势的精细控制&#xff0c;也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档&#xff0c…...

python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)

更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...

04-初识css

一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...

3403. 从盒子中找出字典序最大的字符串 I

3403. 从盒子中找出字典序最大的字符串 I 题目链接&#xff1a;3403. 从盒子中找出字典序最大的字符串 I 代码如下&#xff1a; class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...

(转)什么是DockerCompose?它有什么作用?

一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用&#xff0c;而无需手动一个个创建和运行容器。 Compose文件是一个文本文件&#xff0c;通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列&#xff0c;以便知晓哪些列包含有价值的数据&#xff0c;…...

在Ubuntu24上采用Wine打开SourceInsight

1. 安装wine sudo apt install wine 2. 安装32位库支持,SourceInsight是32位程序 sudo dpkg --add-architecture i386 sudo apt update sudo apt install wine32:i386 3. 验证安装 wine --version 4. 安装必要的字体和库(解决显示问题) sudo apt install fonts-wqy…...

CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)

漏洞概览 漏洞名称&#xff1a;Apache Flink REST API 任意文件读取漏洞CVE编号&#xff1a;CVE-2020-17519CVSS评分&#xff1a;7.5影响版本&#xff1a;Apache Flink 1.11.0、1.11.1、1.11.2修复版本&#xff1a;≥ 1.11.3 或 ≥ 1.12.0漏洞类型&#xff1a;路径遍历&#x…...

Go 语言并发编程基础:无缓冲与有缓冲通道

在上一章节中&#xff0c;我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道&#xff0c;它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好&#xff0…...

MFC 抛体运动模拟:常见问题解决与界面美化

在 MFC 中开发抛体运动模拟程序时,我们常遇到 轨迹残留、无效刷新、视觉单调、物理逻辑瑕疵 等问题。本文将针对这些痛点,详细解析原因并提供解决方案,同时兼顾界面美化,让模拟效果更专业、更高效。 问题一:历史轨迹与小球残影残留 现象 小球运动后,历史位置的 “残影”…...