数据结构与算法 / 系统课时
二叉树的公共祖先
二叉树的公共祖先
最近公共祖先用于寻找同时覆盖两个目标节点的最低祖先节点。本课从递归返回值的含义入手,给出能够校验目标是否存在的完整实现,并说明祖先关系、重复值和复杂度等关键边界。
学习目标
- 理解最近公共祖先的定义与递归搜索过程
- 能根据左右子树返回结果判断当前节点是否为答案
- 能处理目标缺失、目标相同和节点值重复等边界
问题定义
给定一棵普通二叉树和两个目标节点,最近公共祖先是同时包含这两个节点的最低子树根。节点可以是自己的祖先,因此当一个目标位于另一个目标的子树中时,较高的目标节点就是答案。
这里比较的是节点对象身份,而不是节点值。即使两个节点的 value 相同,只要它们是不同对象,也应被视为不同目标。

核心思路
后序遍历先搜索左右子树,再处理当前节点。每次递归同时返回候选节点和已命中的目标数量:某一侧已经命中两个目标时直接保留该侧答案;左右结果与当前节点合计首次达到两个目标时,当前节点就是最近公共祖先。
只返回节点的经典写法通常假设两个目标必然存在。为了避免“只找到一个目标却把它当作答案”,主示例额外返回命中数量,最终只有命中数为 2 才返回结果。
完整可运行示例
python
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def contains(root, target):
if root is None:
return False
return root is target or contains(root.left, target) or contains(root.right, target)
def lowest_common_ancestor(root, first, second):
# 同一个目标节点只需确认它确实存在于树中
if first is second:
return first if contains(root, first) else None
def search(node):
if node is None:
return None, 0
left_node, left_count = search(node.left)
if left_count == 2:
return left_node, 2
right_node, right_count = search(node.right)
if right_count == 2:
return right_node, 2
own_count = 1 if node is first or node is second else 0
total = left_count + right_count + own_count
# 当前节点是第一次汇合两个目标的位置
if total == 2:
return node, 2
if own_count == 1:
return node, 1
if left_count == 1:
return left_node, 1
if right_count == 1:
return right_node, 1
return None, 0
candidate, count = search(root)
return candidate if count == 2 else None
d = Node("D")
e = Node("E")
f = Node("F")
b = Node("B", d, e)
c = Node("C", None, f)
a = Node("A", b, c)
missing = Node("X")
cases = [(d, e), (d, f), (b, e), (d, missing), (e, e)]
for first, second in cases:
result = lowest_common_ancestor(a, first, second)
print(f"{first.value} 与 {second.value}: {result.value if result else None}")预期输出:
text
D 与 E: B
D 与 F: A
B 与 E: B
D 与 X: None
E 与 E: E复杂度与边界
算法最多访问每个节点一次,时间复杂度为 。递归栈深度取决于树高,空间复杂度为 ;平衡树中约为 ,极端链状树中为 。
常见错误包括只比较节点值、默认答案必须严格位于两个目标上方,以及忽略目标不存在的情况。若树节点带有父指针,也可以分别构造祖先链,再像求两个链表交点一样寻找公共节点。
按自己的节奏,确认真正理解。