三亩地 三亩地SAN MU DI · CODE DIARY
交流投稿
ARTICLE DETAIL

日记详情

真实记录编程学习的某一天，欢迎挑你感兴趣的翻一翻。

首页/学习日记/日记详情

二叉树最近公共祖先(LCA)问题解析与实现

发布时间：2026/8/10 3:53:06 三亩地 编程学习日记
二叉树最近公共祖先(LCA)问题解析与实现

1. 项目概述：二叉树最近公共祖先问题

在二叉树相关算法中，最近公共祖先（Lowest Common Ancestor，简称LCA）是一个经典且高频出现的面试题。LeetCode第236题正是考察这个知识点，题目要求：给定一个二叉树和其中的两个节点，找到这两个节点的最近公共祖先。这里的"最近"指的是在二叉树中深度最大的公共祖先节点。

这个问题在实际开发中有诸多应用场景，比如在版本控制系统中寻找两个分支的最近合并点，在DOM树中查找两个元素的共同父节点，或者在家族关系系统中计算两个人的最近共同祖先等。理解并掌握这个问题的解法，不仅能帮助我们应对技术面试，更能提升我们处理树形结构数据的思维能力。

2. 核心概念解析

2.1 二叉树基础回顾

二叉树是每个节点最多有两个子节点的树结构，通常称为左子节点和右子节点。在解决LCA问题时，我们需要明确几个关键概念：

  • 节点深度：从根节点到该节点的路径长度
  • 祖先节点：从根节点到该节点的路径上的所有节点都是其祖先
  • 公共祖先：同时是两个节点祖先的节点
  • 最近公共祖先：距离两个节点最近的公共祖先节点

2.2 最近公共祖先的定义

最近公共祖先是指在一个树结构中，两个给定节点的所有公共祖先中，距离这两个节点最近的那个节点。换句话说，它是这两个节点在树中"交汇"的第一个点。

举个例子，考虑以下二叉树：

3 / \ 5 1 / \ / \ 6 2 0 8 / \ 7 4
  • 节点5和1的LCA是3
  • 节点5和4的LCA是5
  • 节点7和8的LCA是3

3. 递归解法详解

3.1 递归思路分析

递归是解决树形结构问题的天然工具，因为树本身就是递归定义的数据结构。对于LCA问题，我们可以采用后序遍历（左右根）的方式，自底向上地寻找公共祖先。

核心思路是：

  1. 如果当前节点是p或q中的一个，则返回当前节点
  2. 分别在左右子树中递归查找p和q
  3. 如果左右子树都返回非空节点，说明当前节点就是LCA
  4. 如果只有一边返回非空节点，则返回该节点（说明LCA在子树中）

3.2 递归实现代码

class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None class Solution: def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode: # 基准情况：如果root为空或者root就是p或q，直接返回root if not root or root == p or root == q: return root # 递归在左子树中查找 left = self.lowestCommonAncestor(root.left, p, q) # 递归在右子树中查找 right = self.lowestCommonAncestor(root.right, p, q) # 如果左右都找到了，说明当前root就是LCA if left and right: return root # 如果只有一边找到，返回找到的那边 return left if left else right

3.3 递归过程图解

让我们以之前的二叉树为例，查找节点5和1的LCA：

  1. 从根节点3开始，递归进入左子树5
  2. 在节点5，发现匹配p(5)，返回5
  3. 回到节点3，递归进入右子树1
  4. 在节点1，发现匹配q(1)，返回1
  5. 在节点3，左右子树都返回非空，因此3是LCA

4. 算法复杂度分析

4.1 时间复杂度

该算法需要访问二叉树中的每个节点一次，因此时间复杂度为O(N)，其中N是二叉树中的节点数量。这是最优的时间复杂度，因为我们必须检查每个节点才能确定LCA。

4.2 空间复杂度

空间复杂度主要取决于递归调用的栈深度。在最坏情况下（树退化为链表），空间复杂度为O(N)。在平衡二叉树的情况下，空间复杂度为O(logN)。

5. 边界条件与特殊情况处理

5.1 节点不存在的情况

在实际应用中，我们需要考虑p或q可能不在树中的情况。上述基础解法假设两个节点都在树中。如果需要处理节点不存在的情况，可以修改算法：

class Solution: def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode: self.found_p = False self.found_q = False result = self.findLCA(root, p, q) return result if (self.found_p and self.found_q) else None def findLCA(self, root, p, q): if not root: return None left = self.findLCA(root.left, p, q) right = self.findLCA(root.right, p, q) # 检查当前节点是否是p或q if root == p: self.found_p = True return root if root == q: self.found_q = True return root if left and right: return root return left if left else right

5.2 其他边界情况

  • 当p就是q的祖先时，应该返回p
  • 当q就是p的祖先时，应该返回q
  • 当树为空时，应该返回None
  • 当p或q为None时，应该返回None

6. 非递归解法对比

6.1 使用父指针的迭代方法

虽然递归解法简洁优雅，但在某些情况下（比如树非常深时），我们可能需要考虑迭代解法。一种常见的方法是使用父指针：

  1. 从根节点开始遍历树，记录每个节点的父指针
  2. 从p开始向上访问所有祖先，存入集合
  3. 从q开始向上访问祖先，第一个在集合中的就是LCA
class Solution: def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode: stack = [root] parent = {root: None} # 迭代直到找到p和q的父指针 while p not in parent or q not in parent: node = stack.pop() if node.left: parent[node.left] = node stack.append(node.left) if node.right: parent[node.right] = node stack.append(node.right) # 收集p的所有祖先 ancestors = set() while p: ancestors.add(p) p = parent[p] # 查找q的祖先中第一个在p的祖先集合中的节点 while q not in ancestors: q = parent[q] return q

6.2 两种方法的比较

方法时间复杂度空间复杂度适用场景
递归O(N)O(H)代码简洁，树深度不大时
迭代+父指针O(N)O(N)树很深可能栈溢出时

7. 实际应用与变种问题

7.1 实际应用场景

  1. 版本控制系统：Git中寻找两个分支的最近共同提交
  2. DOM操作：查找两个HTML元素的最近共同父元素
  3. 计算生物学：在系统发育树中寻找物种的最近共同祖先
  4. 社交网络：计算两个人的最近共同好友或关系

7.2 常见变种问题

  1. 二叉搜索树的LCA：利用BST性质可以更高效地解决
  2. 多叉树的LCA：原理类似，但需要考虑多个子节点
  3. 带父指针的树的LCA：可以转化为链表相交问题
  4. 多个节点的LCA：扩展为寻找多个节点的最近公共祖先

8. 常见错误与调试技巧

8.1 新手常见错误

  1. 混淆节点值比较和节点比较：应该比较节点对象而非节点值

    • 错误：if root.val == p.val
    • 正确：if root == p

  2. 忽略递归基准条件：忘记处理root为None的情况

  3. 错误理解"最近"：返回了第一个找到的公共祖先而非最近的

  4. 未考虑节点不在树中的情况：当p或q不在树中时应返回None

8.2 调试技巧

  1. 可视化递归过程：画出递归调用树，标注每次递归的返回值
  2. 打印调试信息：在递归函数中添加打印语句，显示当前节点和递归深度
  3. 使用小型测试用例：先从简单的3节点树开始测试
  4. 边界测试：测试p或q是根节点、p是q的祖先等情况

9. 性能优化与进阶思考

9.1 多次查询优化

如果需要多次查询不同节点对的LCA，可以考虑预处理技术：

  1. 欧拉序+RMQ：将LCA问题转化为RMQ问题
  2. Tarjan离线算法：一次性处理所有查询
  3. 二进制提升法：预处理每个节点的2^k级祖先

这些方法可以将单次查询时间优化到O(1)或O(logN)，但需要额外的预处理时间和空间。

9.2 非二叉树扩展

对于一般的树结构（不一定是二叉树），LCA问题同样适用。常用的解法包括：

  1. 转化为RMQ问题：通过DFS遍历记录欧拉序和深度序列
  2. 使用并查集：Tarjan离线算法的核心
  3. 树链剖分：将树分解为多条链，加速查询

10. 面试技巧与实战建议

10.1 面试中的解题步骤

  1. 明确问题：确认输入输出，询问边界条件（节点是否一定存在？树是否可能为空？）
  2. 举例说明：画一个小型例子，手动计算LCA
  3. 提出暴力解法：先给出直观解法（如记录路径然后比较）
  4. 优化思路：分析暴力解法的问题，引出递归/迭代优化
  5. 代码实现：编写清晰、模块化的代码
  6. 测试验证：用多个测试用例验证代码正确性

10.2 常见面试问题

  1. 如何证明你的算法是正确的？
  2. 如果树非常大，递归解法会有什么问题？
  3. 如何修改算法处理节点可能不存在的情况？
  4. 在二叉搜索树中，如何更高效地解决这个问题？
  5. 如果每个节点都有指向父节点的指针，如何优化解法？

11. 相关题目推荐

为了巩固对LCA问题的理解，建议练习以下LeetCode题目：

  1. 235. 二叉搜索树的最近公共祖先：利用BST性质优化
  2. 1644. 二叉树的最近公共祖先 II：处理节点可能不存在的情况
  3. 1650. 二叉树的最近公共祖先 III：节点有父指针的情况
  4. 1676. 二叉树的最近公共祖先 IV：查找多个节点的LCA
  5. 1123. 最深叶节点的最近公共祖先：LCA变种问题

12. 个人经验分享

在实际面试和刷题过程中，我发现LCA问题有几个关键点需要特别注意：

  1. 递归终止条件：一定要先处理root为None或root等于p/q的情况，这个顺序不能错
  2. 返回值理解：递归函数返回的不是最终的LCA，而是表示当前子树中是否包含p或q
  3. 测试用例设计：要包括p和q在不同侧、同侧、一个是另一个祖先等情况
  4. 空间优化：在面试中如果被问到，可以讨论如何用迭代替代递归避免栈溢出

一个容易忽略的细节是，当p就是q的祖先时，算法应该返回p而不是继续向上查找。这在递归解法中是自然处理的，但在某些迭代实现中可能需要特殊处理。

编程学习 学习日记 实战经验
← 返回列表