数据结构与算法 / 系统课时

二叉树的公共祖先

二叉树的公共祖先

最近公共祖先用于寻找同时覆盖两个目标节点的最低祖先节点。本课从递归返回值的含义入手,给出能够校验目标是否存在的完整实现,并说明祖先关系、重复值和复杂度等关键边界。

学习目标

  • 理解最近公共祖先的定义与递归搜索过程
  • 能根据左右子树返回结果判断当前节点是否为答案
  • 能处理目标缺失、目标相同和节点值重复等边界

问题定义

给定一棵普通二叉树和两个目标节点,最近公共祖先是同时包含这两个节点的最低子树根。节点可以是自己的祖先,因此当一个目标位于另一个目标的子树中时,较高的目标节点就是答案。

这里比较的是节点对象身份,而不是节点值。即使两个节点的 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

复杂度与边界

算法最多访问每个节点一次,时间复杂度为 O(n)O(n)。递归栈深度取决于树高,空间复杂度为 O(h)O(h);平衡树中约为 O(log⁡n)O(\log n),极端链状树中为 O(n)O(n)。

常见错误包括只比较节点值、默认答案必须严格位于两个目标上方,以及忽略目标不存在的情况。若树节点带有父指针,也可以分别构造祖先链,再像求两个链表交点一样寻找公共节点。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

二叉树的公共祖先

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通