新闻详情

新闻详情

首页 / 资讯中心 / 详情

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

发布时间:2026/11/20 0:09:53来源:尧图网络
【二叉树-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)
网站建设高端定制企业官网
RELATED

相关资讯

更多精彩内容,欢迎继续阅读

较早相关资讯

最新相关资讯

【外设】之大彩串口显示屏 2026/11/18 21:21:17

【外设】之大彩串口显示屏

大彩串口屏初步使用 1 .官网下载 STM32 屏幕 GUI 设计资料 http://www.gz-dc.com/category/typeid/4112 找到 STM32 Keil 工程,移植相关代码因项目而异进行移植,由于项目简单,本人只对用到的指令接口进行修改。 比如:注意事项&…

阅读更多 →
无法下载Windows系统iso文件 2026/11/19 15:17:14

无法下载Windows系统iso文件

当我遇到这个问题的时候,我打开了一个网站: 登录 然后我打算下载的时候: 突然那个官方的连接就可以下载了:

阅读更多 →
【清华代码熊】DeepSeek V4.1 Flash 后训练详解 2026/11/19 20:26:12

【清华代码熊】DeepSeek V4.1 Flash 后训练详解

📌 上期解析了 DeepSeek V4.1 Flash 模型架构改进,本期解析 DeepSeek V4.1 Flash 预训练/后训练技术: 🌟 预训练:45T 文本 多模态混合语料、直接训练 sparse attention(取消 DeepSeek V4 的 dense 冷启动&…

阅读更多 →
Shuffle-R1: Efficient RL framework for Multimodal Large Language Models via Data-centric Dynamic ... 2026/11/19 15:16:22

Shuffle-R1: Efficient RL framework for Multimodal Large Language Models via Data-centric Dynamic ...

文章主要内容和创新点 主要内容 本文聚焦于多模态大语言模型(MLLM)强化学习(RL)训练中的效率问题,提出了一个名为Shuffle-R1的框架。研究发现,当前RL训练存在两个关键缺陷: 优势值坍缩(Advantage Collapsing):批次中大多数优势值集中在零附近,导致有效梯度信号被淹…

阅读更多 →
PRvL: Quantifying the Capabilities and Risks of Large Language Models for PII Redaction 2026/11/19 18:03:31

PRvL: Quantifying the Capabilities and Risks of Large Language Models for PII Redaction

一、文章主要内容总结 本文聚焦于利用大型语言模型(LLMs)实现个人身份信息(PII)脱敏的研究,旨在解决传统脱敏方法(如基于规则的系统、领域特定命名实体识别(NER)模型)泛化能力差、跨格式/跨语境适应性弱的问题。 研究通过全面评估多种LLM架构(包括密集型LLM(D-LLM…

阅读更多 →
LLaVA-RE: Binary Image-Text Relevancy Evaluation with Multimodal Large Language Model 2026/11/18 21:21:16

LLaVA-RE: Binary Image-Text Relevancy Evaluation with Multimodal Large Language Model

文章主要内容和创新点 主要内容 本文聚焦于二进制图像-文本相关性评估任务(判断图像与文本“相关”或“不相关”),针对该任务中文本格式多样、相关性定义随场景变化等挑战,提出了基于多模态大语言模型(MLLM)的解决方案LLaVA-RE。 模型设计:LLaVA-RE基于LLaVA 1.5架构,…

阅读更多 →

今日资讯

本周资讯

本月资讯

看完文章仍有疑问?

联系尧图顾问,获取一对一建站咨询

立即免费咨询 📞 400-888-8888
📞 ✉