1. 简介
二叉树在计算机科学中有广泛的应用，为了充分发挥其作用，我们需要一系列高效的算法来对其进行操作。其中一个常见问题就是找出两个节点的最低公共祖先（LCA）。
本篇文章将围绕这一问题展开讲解，适用于普通二叉树的情况。
2. 问题描述
给定一棵二叉树和两个节点，我们的目标是找出这两个节点的最低公共祖先。
回顾一下，二叉树是一种特殊的树结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。树结构保证任意两个节点之间只有一条路径相连。
因此，任意两个节点都至少有一个公共祖先 —— 根节点。但我们要找的是它们的最低公共祖先，即路径上最靠近这两个节点的那个共同祖先。
举个例子：
- 节点
H和O的 LCA 是根节点A。 - 节点
D和E的 LCA 是B。 - 如果其中一个节点是另一个节点的祖先（如
C和L），那么 LCA 就是那个父节点本身。
3. LCA 算法思路
解决这个问题的一个直观方法是：
- 找出从根节点到每个目标节点的路径。
- 比较这两条路径，找到最后一个相同的节点，即为 LCA。
3.1 获取路径
要获取从根节点到目标节点的路径，我们可以从目标节点出发，通过其父节点向上回溯，直到根节点。为此，我们需要先构建一个父节点映射表。
3.2 构建父节点映射
使用 BFS 遍历整棵树，记录每个节点的父节点即可完成构建。这一步是算法中最耗时的部分。
3.3 比较路径找 LCA
一旦我们有了两个节点的路径，就可以逐个比较路径中的节点，直到出现不一致为止。最后一个一致的节点就是 LCA。
✅ 算法流程图示意
- 找路径：从节点向上回溯父节点
- 找父节点：BFS 遍历树，记录每个节点的父节点
- 找 LCA：比较两条路径中最后一个相同的节点
4. 伪代码实现
4.1 获取路径
algorithm FindPath(Root, Node, parents):
// INPUT: 树根节点、目标节点、父节点映射
// OUTPUT: 从根到目标节点的路径
temp <- Node
path <- [temp]
while temp != Root:
temp <- parents[temp]
path <- temp + path
return path
4.2 构建父节点映射
algorithm FindParents(Root):
// INPUT: 树根节点
// OUTPUT: 父节点映射表
parents <- {Root: NULL}
BFS_Q <- []
enqueue(Root, BFS_Q)
while size(BFS_Q) > 0:
temp <- dequeue(BFS_Q)
if temp.left != NULL:
enqueue(temp.left, BFS_Q)
parents[temp.left] <- temp
if temp.right != NULL:
enqueue(temp.right, BFS_Q)
parents[temp.right] <- temp
return parents
4.3 查找 LCA 主函数
algorithm FindLCA(Root, Node1, Node2):
// INPUT: 树根节点、两个目标节点
// OUTPUT: 最低公共祖先节点
parents <- FindParents(Root)
path1 <- FindPath(Root, Node1, parents)
path2 <- FindPath(Root, Node2, parents)
index <- 1
lca <- Root
while index < minimum(size(path1), size(path2)):
if path1[index] = path2[index]:
lca <- path1[index]
index <- index + 1
else:
break
return lca
5. 时间与空间复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 构建父节点映射（BFS） | O(n) | O(n) |
| 获取路径 | O(h) | O(h) |
| 比较路径找 LCA | O(h) | O(1) |
✅ 总体复杂度
- 时间复杂度：O(n)（最坏情况，树退化为链表）
- 空间复杂度：O(n)
⚠️ 如果父节点映射已知，复杂度可以降为 O(h)，若树是平衡的，则为 O(log n)
6. 总结
本文介绍了在二叉树中查找两个节点的最低公共祖先（LCA）的算法实现。
我们通过构建父节点映射、获取路径、比较路径三步走的方式，实现了 LCA 的查找。
虽然这个算法的时间复杂度是 O(n)，但如果树结构是静态的且 LCA 查询频繁，可以考虑提前构建父节点映射，以优化后续查询效率。
✅ 踩坑提醒：在实际编码中，注意节点是否存在于树中，避免空指针异常。此外，路径比较时注意边界处理。