普通二叉树 —— 最近公共祖先问题解析(Leetcode 236)

article/2025/7/14 7:12:24

🏠个人主页:尘觉主页

文章目录

  • 普通二叉树 —— 最近公共祖先问题解析(Leetcode 236)
    • 🧠 问题理解
      • 普通二叉树与 BST 的区别:
    • 💡 解题思路
      • 关键思想:
      • 📌 举个例子:
    • 🔍 图示解析
    • ✅ Java 实现
      • 🛠️ 核心判断逻辑:
    • 🚀 时间复杂度分析
    • 📝 总结

普通二叉树 —— 最近公共祖先问题解析(Leetcode 236)

在上一节中我们学习了如何在二叉查找树(BST)中寻找两个节点的最近公共祖先(Lowest Common Ancestor,简称 LCA)。
本节我们将进一步拓展到普通二叉树的场景,即无序结构的树,这就不能再依赖节点的大小关系进行剪枝优化了。

本文将结合 Leetcode 第 236 题 Lowest Common Ancestor of a Binary Tree,分析如何在任意二叉树中寻找两个节点的最近公共祖先。


🧠 问题理解

题目描述:
给定一棵二叉树的根节点 root 和两个节点 pq,请找出它们的最近公共祖先。

普通二叉树与 BST 的区别:

  • 普通二叉树不具备节点值的有序性。
  • 所以不能通过节点值大小来判断节点在左子树还是右子树,只能遍历整个结构。

💡 解题思路

我们可以采用后序遍历(Post-order Traversal)+ 递归回溯的方法来解决这个问题。

关键思想:

  • 如果当前节点是空,直接返回 null;

  • 如果当前节点就是 pq,说明找到了目标节点之一,直接返回当前节点;

  • 否则分别递归左右子树查找 pq

    • 如果左右子树递归结果都非空,说明当前节点是最近公共祖先;
    • 如果有一个子树非空,返回非空子树的结果;
    • 如果两个子树都为空,返回 null。

📌 举个例子:

  • 左子树找到 p,右子树找到 q,那么当前节点就是最近公共祖先;
  • 左右子树只有一个有结果,说明两个节点都位于那一侧;

🔍 图示解析

如图所示,若我们查找节点 5 和 1 的最近公共祖先,从根节点 3 出发,左子树返回 5,右子树返回 1,两个都非空,因此节点 3 就是 LCA。


✅ Java 实现

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if (root == null || root == p || root == q)return root;TreeNode left = lowestCommonAncestor(root.left, p, q);TreeNode right = lowestCommonAncestor(root.right, p, q);return left == null ? right : right == null ? left : root;
}

🛠️ 核心判断逻辑:

return left == null ? right : right == null ? left : root;

这行代码的含义是:

  • 若左为空,说明 p 和 q 都在右子树;
  • 若右为空,说明 p 和 q 都在左子树;
  • 若左右都不为空,说明当前节点为最近公共祖先。

🚀 时间复杂度分析

  • 时间复杂度:O(n),需要遍历整棵树;
  • 空间复杂度:O(h),递归栈深度,h 为树的高度,最坏为 O(n)。

📝 总结

普通二叉树中寻找最近公共祖先,不再依赖节点值的有序性,而是完全依靠递归回溯地查找两个目标节点的位置,再根据左右子树的返回值来判断 LCA。

🌱 思考建议:本题的核心思想——“在左右子树分别查找目标节点”是树结构常见的递归套路,掌握后可以类比解决其他二叉树相关的问题。


欢迎点赞 👍、收藏 ⭐、评论 💬 支持,后续我将持续分享更多高频面试题与 Leetcode 解题技巧!

如果你需要该文章的 Markdown 格式或想继续深入如 N 个节点的最近公共祖先问题,也欢迎留言讨论!


😁热门专栏推荐
想学习vue的可以看看这个

java基础合集

数据库合集

redis合集

nginx合集

linux合集

手写机制

微服务组件

spring_尘觉

springMVC

mybits

等等等还有许多优秀的合集在主页等着大家的光顾感谢大家的支持

🤔欢迎大家加入我的社区 尘觉社区

文章到这里就结束了,如果有什么疑问的地方请指出,诸佬们一起来评论区一起讨论😁
希望能和诸佬们一起努力,今后我们一起观看感谢您的阅读🍻
如果帮助到您不妨3连支持一下,创造不易您们的支持是我的动力🤞

img


http://www.hkcw.cn/article/fCerkRZGtd.shtml

相关文章

Dify 部署问题处理

Dify介绍 Dify 是一款开源的大语言模型(LLM) 应用开发平台。它融合了后端即服务(Backend as Service)和 LLMOps 的理念,使开发者可以快速搭建生产级的生成式 AI 应用。即使你是非技术人员,也能参与到 AI 应用的定义和数据运营过程…

《操作系统真相还原》——中断

可以毫不夸张的说,操作系统离不开中断 此时我们将中断处理程序放在了汇编文件中了,很显然我们不能很方便的编写中断处理程序,不如在汇编程序里调用c函数。 在这个感觉过可以在c语言中直接内联汇编完成这些。 定时器 将时钟中断的频率提高后…

腾讯位置商业授权沿途搜索服务开发指南

概述 通过本服务检索某段道路附近的POI信息,可配合路线规划,为用户提供沿途服务区、加油站等搜索功能。 注: 1、本服务属于高级付费服务,如需试用请提交商务合作开通服务试用。 2、本接口有大小限制,接口长度不能超…

内容中台的实施基石是什么?

标准化流程体系构建 在企业内容中台建设中,标准化流程体系是确保内容生产、管理和分发效率的核心框架。通过定义元数据规范、内容分类规则及跨部门协作机制,能够实现从内容创建到归档的全链路标准化运作。例如,Baklib作为支持团队协作与权限…

信息安全管理与评估2024山东卷WAF答案

需要其他赛题解析的可联系博主

[免费]微信小程序网上花店系统(SpringBoot后端+Vue管理端)【论文+源码+SQL脚本】

大家好,我是java1234_小锋老师,看到一个不错的微信小程序网上花店系统(SpringBoot后端Vue管理端)【论文源码SQL脚本】,分享下哈。 项目视频演示 【免费】微信小程序网上花店系统(SpringBoot后端Vue管理端) Java毕业设计_哔哩哔哩_bilibili 项…

定制开发开源AI智能名片驱动下的海报工厂S2B2C商城小程序运营策略——基于社群口碑传播与子市场细分的实证研究

摘要 本文聚焦“定制开发开源AI智能名片S2B2C商城小程序”技术与海报工厂业务的融合实践,探讨其如何通过风格化海报矩阵的精细化开发、AI技术驱动的用户体验升级,以及S2B2C模式下的社群裂变机制,实现“工具功能-社交传播-商业变现”的生态…

制作个人Github学术主页

1.fork一个模板 从模板网站Jekyll Themes fork一个模板,并在repository name里填入yourname.github.io 2.生成自己的site 按顺序点击以下按钮,修改Branch为master /root 然后点击save ,等待一会后刷新,便会生成一个新的site。 3.…

无法访问公网或 DNS 解析失败怎么办?

当云服务器无法访问公网或DNS 解析失败时,可能会导致无法 ping 外网、不能下载软件或无法访问网站。下面是详细的排查和解决方法: 莱卡云 🧭 一、问题现象说明 问题表现无法访问公网ping 8.8.8.8 不通DNS 解析失败ping www.baidu.com 报错“…

简道云--第一个表单

一、创建表单 新建应用--创建空白应用--名称--新建表单--创建空白表单 二、表单内容 三、表单发布及数据收集 表单公共发布案例:员工基础信息表

web架构2------(nginx多站点配置,include配置文件,日志,basic认证,ssl认证)

一.前言 前面我们介绍了一下nginx的安装和基础配置,今天继续来深入讲解一下nginx的其他配置 二.nginx多站点配置 一个nginx上可以运行多个网站。有多种方式: http:// ip/域名 端口 URI 其中,ip/域名变了,那么网站入口就变了…

深度学习|pytorch基本运算-hadamard积、点积和矩阵乘法

【1】引言 pytorch对张量的基本运算和线性代数课堂的教学有一些区别,至少存在hadamard积、点积和矩阵乘法三种截然不同的计算方法。 【2】hadamard积 hadamard积是元素对位相乘,用“*”连接张量,代码: # 导入包 import torch …

uniapp路由跳转toolbar页面

需要阅读uview-ui的API文档 注意需要使用type参数设置后才起作用 另外route跳转的页面会覆盖toolbar工具栏 toConternt(aid) {console.log(aid:, aid)this.$u.route({// url: "pages/yzpg/detail",url: "pages/yzappl/index",// url: "pages/ind…

数据结构哈希表总结

349. 两个数组的交集 力扣题目链接(opens new window) 题意:给定两个数组,编写一个函数来计算它们的交集。 说明: 输出结果中的每个元素一定是唯一的。 我们可以不考虑输出结果的顺序。 public int[] intersection(int[] nums1, int[] num…

【深度学习新浪潮】多模态模型如何处理任意分辨率输入?

多模态模型处理任意分辨率输入的能力主要依赖于架构设计的灵活性和预处理技术的结合。以下是核心方法及技术细节: 一、图像模态的分辨率处理 1. 基于Transformer的可变补丁划分(ViT架构) 补丁化(Patch Embedding): 将图像分割为固定大小的补丁(如1616或3232像素),不…

CSS之动画(奔跑的熊、两面反转盒子、3D导航栏、旋转木马)

一、 2D转换 1.1 transform: translate( ) 转换(transform) 是CSS3中具有颠覆性的特征之一,可以实现元素的位移、旋转、缩放等效果 移动:translate 旋转:rotate 缩放:scale 下图为2D转换的坐标系 回忆…

使用 MCP 将代理连接到 Elasticsearch 并对索引进行查询

本文是之前文章 “将代理连接到 Elasticsearch 使用模型上下文协议” 的扩展。在这里,我们将以详细的步骤来一步一步地展示如何安装 MCP Server 及使用 MCP 服务器和我们的 Elasticsearch 中的数据来进行对话。 安装 Elasticsearch 及 Kibana 如果你还没有安装好你…

PMI Suite V5.9.125 (Byos and Byosphere)2025年5月15日版本PMI Suite V5.9

1、完整质量分析 Intact Mass™工作流程提供自动MS/MS光谱注释、MS级反卷积和鉴定,与传统的自下而上方法相比,减少了数据分析所需的时间。 2、肽水平分析 鉴定复杂样品中的蛋白质和修饰肽。大幅缩短以肽为中心的工作流程的分析时间 3、色谱图分析 将…

MDP的curriculums部分

文章目录 1. isaaclab中的curriculums1.1 modify_reward_weight1.1.1 函数功能1.1.2 参数详解1.1.3 函数逻辑1.1.4 如何使用 2. isaaclab_task中的curriculums2.1 terrain_levels_vel2.1 功能概述2.2 函数参数2.3 函数逻辑 3. robot_lab中的curriculums3.1 command_levels_vel …

【AUTOSAR OS】事件机制解析:定义、实现与应用

文章目录 一、Event的定义与作用二、核心数据结构三、重要函数实现与原理1. **事件初始化 Os_InitEvent()**2. **设置事件 SetEvent()/Os_SetEvent()**3. **等待事件 WaitEvent()/Os_WaitEvent()**4. **清除事件 ClearEvent()**5. **获取事件状态 GetEvent()** 四、应用示例&am…