算法 - 二叉树的最近公共祖先 (LCA)

Posted on

1. 题目

给定一个二叉树，找到树中两个指定节点 p、q 的最近公共祖先（Lowest Common Ancestor）。

最近公共祖先定义：对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。

示例:

1
2
3
4
5
6
7
8
9
10
        3
       / \
      5   1
     / \ / \
    6  2 0  7
      / \
     7   4

输入: p = 5, q = 1  -> 输出: 3
输入: p = 5, q = 4  -> 输出: 5（5 是 4 的祖先，也是自身，故为最近公共祖先）

2. 解题思路

2.1 通用二叉树：后序递归（最优）

自底向上。定义 lca(root, p, q) 返回「以 root 为根的子树中，p 和 q 的最近公共祖先或其中之一」。

对当前节点：

  • base case：root 为空，或 root === p 或 root === q，直接返回 root。

  • 递归左右子树得到 left、right。

  • 分类讨论：

    • left 和 right 都非空 → p、q 分居两侧，当前 root 即为 LCA。
    • 只有一侧非空 → 说明两节点都在那一侧（或找到一个就把它返回），返回那侧的结果。
    • 都空 → 返回 null。

  • 时间复杂度：O(n)。

  • 空间复杂度：O(h) 递归栈。

2.2 若是二叉搜索树（BST 235 题）

利用有序性：从根开始，p、q 都小于当前值走左、都大于走右，一旦分裂或等于即为 LCA，无需递归，O(h) 时间 O(1) 空间。

3. TypeScript 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
function lowestCommonAncestor(
    root: TreeNode | null,
    p: TreeNode,
    q: TreeNode
): TreeNode | null {
    if (root === null || root === p || root === q) return root;

    const left = lowestCommonAncestor(root.left, p, q);
    const right = lowestCommonAncestor(root.right, p, q);

    // p、q 分居两侧，当前节点即最近公共祖先
    if (left !== null && right !== null) return root;
    // 否则返回非空的那一侧
    return left !== null ? left : right;
}

// BST 版本
function lowestCommonAncestorBST(
    root: TreeNode | null,
    p: TreeNode,
    q: TreeNode
): TreeNode | null {
    let curr = root;
    while (curr) {
        if (p.val < curr.val && q.val < curr.val) {
            curr = curr.left;
        } else if (p.val > curr.val && q.val > curr.val) {
            curr = curr.right;
        } else {
            return curr; // 分裂点或命中其一
        }
    }
    return null;
}

4. 面试延伸

  • 理解「一个节点是自身祖先」：所以 p 是 q 的祖先时，LCA 就是 p，这正是 base case 命中 root === p 后直接返回的原因。
  • 若 p、q 不一定存在？ 需要额外标记是否都找到，或用父指针法（记录路径再比对）。
  • 多叉树 LCA / 带 parent 指针的 LCA（相交链表思路）：把两条到根的路径当作「找第一个公共节点」，与 [相交链表] 同源。
  • 递归返回值的语义要讲清：它同时承担了「找到一个就上报」和「两侧都命中就在根结算」两种职责，是本题最精妙处。

难度：中等 | LeetCode 236 题 | 后序递归经典