首页/新闻资讯/正文详情

【二叉树-11】236.二叉树的最近公共祖先

发布时间:2026/9/26 16:11:16 来源:云帆数科 栏目:资讯中心
【二叉树-11】236.二叉树的最近公共祖先
题目描述给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为“对于有根树 T 的两个节点 p、q最近公共祖先表示为一个节点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大一个节点也可以是它自己的祖先。”示例 1输入root [3,5,1,6,2,0,8,null,null,7,4], p 5, q 1输出3解释节点 5 和节点 1 的最近公共祖先是节点 3 。示例 2输入root [3,5,1,6,2,0,8,null,null,7,4], p 5, q 4输出5解释节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。示例 3输入root [1,2], p 1, q 2输出1解题思路方法递归后序遍历核心思路对于任意节点root判断 p 和 q 的位置p 和 q 都在左子树→ LCA 在左子树p 和 q 都在右子树→ LCA 在右子树p 和 q 分别在左右子树→ LCA 就是当前节点当前节点就是 p 或 q→ LCA 就是当前节点递归函数定义TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)返回值含义如果root是 p 或 q返回root如果root的左右子树分别包含 p 和 q返回root如果root的左右子树只有一边包含 p 或 q返回那一边的结果如果都不包含返回nullptr具体过程示例3 / \ 5 1 / \ / \ 6 2 0 8 / \ 7 4 p 5, q 4 递归过程: 1. 节点3: 左子树返回5, 右子树返回null → 返回5 2. 节点5: 左子树返回null, 右子树返回4 → 返回5因为5是p 3. 节点2: 左子树返回7, 右子树返回4 → 返回2左右都非空 最终: 5 ✅代码实现class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { // 终止条件 if (root nullptr) return nullptr; if (root p || root q) return root; // 递归左右子树 TreeNode* left lowestCommonAncestor(root-left, p, q); TreeNode* right lowestCommonAncestor(root-right, p, q); // 左右都非空说明 p 和 q 分别在两侧当前节点就是 LCA if (left ! nullptr right ! nullptr) return root; // 只有一边非空返回那一边 return (left ! nullptr) ? left : right; } };复杂度分析维度复杂度说明时间复杂度O(n)最坏情况遍历所有节点空间复杂度O(h)递归栈深度h 是树的高度空间复杂度说明最坏情况链状树O(n)平均情况平衡树O(log n)关键细节1. 为什么root p || root q就返回root因为如果当前节点就是 p 或 q它可能是 LCA如果另一个在它的子树中或者它不是 LCA但需要向上传递我找到了 p 或 q这个信息2. 为什么left ! nullptr right ! nullptr时返回root因为左子树找到了 p 或 q右子树找到了另一个说明 p 和 q分别在两侧当前节点就是它们的最近公共祖先3. 为什么最后返回left ! nullptr ? left : right如果只有左子树非空说明 p 和 q都在左子树返回左子树的结果如果只有右子树非空说明 p 和 q都在右子树返回右子树的结果如果都为空返回nullptr总结要点说明核心思想后序遍历判断 p 和 q 的位置关键判断左右都非空 → 当前节点是 LCA时间复杂度O(n)空间复杂度O(h)

相关推荐

FAST 官方文档站 fast-site 的演进与构建实践:从 0.2.0 到 0.6.2 的变更记录解读与当前 Eleventy 架构剖析
FAST 官方文档站 fast-site 的演进与构建实践:从 0.2.0 到 0.6.2 的变更记录解读与当前 Eleventy 架构剖析

前端UI组件 【免费下载链接】fast The adaptive interface system for modern web experiences. 项目地址: https://gitcode.com/gh_mirrors/fa/fast 点击查看 免费下载 FAST(The adaptive interface system for modern web experiences)仓库… · 2026/9/26 16:11:16

Claude Code 新标准:三分钟了解什么是 Agent Skills?
Claude Code 新标准:三分钟了解什么是 Agent Skills?

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/26 16:11:16

从零构建 Browser Agent 实战:AgentScope + Playwright MCP 配置与验证全流程(含 TaoToken 统一 Key 接入)
从零构建 Browser Agent 实战:AgentScope + Playwright MCP 配置与验证全流程(含 TaoToken 统一 Key 接入)

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/26 16:11:10

Java后端实现维度指标列表:从模型设计到性能优化实战
Java后端实现维度指标列表:从模型设计到性能优化实战

1. 从需求到架构:维度指标列表到底在解决什么问题做了几年Java后端,你会发现一个高频场景反复出现:运营要一个数据看板,老板要看核心指标,产品要分析不同维度的用户行为。前端的最终呈现往往就是一张“维度指标列表”—… · 2026/9/26 16:50:15

Sublime Text 3 插件完美配置指南:7个核心插件与深度调优
Sublime Text 3 插件完美配置指南:7个核心插件与深度调优

简介:本资源是面向Web前端与全栈开发者的Sublime Text 3「开箱即用」插件集成版,专为提升编码效率与开发体验而深度配置。资源已预装涵盖代码高亮、智能补全、项目管理、格式化、Git集成、多光标编辑等十大类核心插件(如Package Control、Emm… · 2026/9/26 16:50:15

同城租房系统实战:Spring Boot+Vue3前后端分离完整实现
同城租房系统实战:Spring Boot+Vue3前后端分离完整实现

做这个同城租房系统,起因其实很实在——很多朋友在准备Java课程设计或者毕业设计时,最头疼的不是写代码,而是找不到一个业务逻辑完整、能真正跑起来的选题。同城租房系统恰恰是这种典型项目:它的业务足够闭环,从用户注… · 2026/9/26 16:50:15

小白也能实现智能问数智能体:用 universal-db-mcp 在 Coze 中搭建 AskDB 问数智能体
小白也能实现智能问数智能体:用 universal-db-mcp 在 Coze 中搭建 AskDB 问数智能体

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/26 16:50:15

虚拟机Ubuntu中文输入法配置:从IBus到Fcitx的完整指南
虚拟机Ubuntu中文输入法配置:从IBus到Fcitx的完整指南

如果让你在虚拟机里装Ubuntu,我猜十有八九会撞上这个场景:系统界面切成了中文,输入法面板上也挂着拼音,可每次按CtrlSpace就是切不出来,偶尔切出来了,打了半天全是字母。网上教程很多,但大多数帖… · 2026/9/26 16:50:15

Codex 界面反复显示「正在重新连接 n/5」:config.toml 骨架与排查清单
Codex 界面反复显示「正在重新连接 n/5」:config.toml 骨架与排查清单

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/26 16:50:09

数据库课后习题答案别硬背:当测试用例集刷,效率翻倍
数据库课后习题答案别硬背:当测试用例集刷,效率翻倍

简介:万常选版《数据库原理与设计》课后习题答案资源,覆盖第2至6章及第9章,适合正在学习关系模型、数据库建模、关系数据理论与模式求精的本科生、自学者作为复习与自测材料。压缩包共7个文件,含3个doc参考答案、2个sql示例脚本、… · 2026/9/26 0:00:21

OpenClaw 替代品?Hermes Agent 踩坑实录:macOS 飞书接入 TaoToken 配置
OpenClaw 替代品?Hermes Agent 踩坑实录:macOS 飞书接入 TaoToken 配置

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/26 0:00:40

向下兼容与向上兼容:接口设计中的兼容性策略与工程实践
向下兼容与向上兼容:接口设计中的兼容性策略与工程实践

一次版本升级事故,是很多团队绕不过去的坎。线上环境里,服务端明明已经上线了新版接口,老的移动端还在照着旧文档传参数。请求一到网关,校验直接拒绝,用户操作失败,客服群炸了锅,开发群里开始互… · 2026/9/26 0:00:46

了解更多?预约专属演示

我们的顾问将为您一对一讲解产品与方案

企业微信二维码