当前位置：首页 > news >正文

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

news 2026/8/10 3:53:06

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问题，我们可以采用后序遍历（左右根）的方式，自底向上地寻找公共祖先。

核心思路是：

如果当前节点是p或q中的一个，则返回当前节点
分别在左右子树中递归查找p和q
如果左右子树都返回非空节点，说明当前节点就是LCA
如果只有一边返回非空节点，则返回该节点（说明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：

从根节点3开始，递归进入左子树5
在节点5，发现匹配p(5)，返回5
回到节点3，递归进入右子树1
在节点1，发现匹配q(1)，返回1
在节点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 使用父指针的迭代方法

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

从根节点开始遍历树，记录每个节点的父指针
从p开始向上访问所有祖先，存入集合
从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