树中两个节点的最低公共祖先

1. 概述

在本文中，我们将讨论最低公共祖先（Lowest Common Ancestor, LCA）问题。我们会从基本定义讲起，然后介绍几种在有根树中查找两个节点最低公共祖先的方法。

2. 定义

在有根树中，两个节点 u 和 v 的最低公共祖先（LCA）是指同时是 u 和 v 祖先的最深节点。
所谓祖先，指的是从树根到该节点路径上的所有节点（包括该节点本身）。

举个例子，看下面这棵树，根节点为 1：

Tree1

我们要找节点 7 和 11 的 LCA。它们的共同祖先有节点 1 和 2，其中节点 2 更深，所以 LCA 是节点 2，记作 LCA(7, 11) = 2。

3. 暴力法（Naive Approach）

3.1. 核心思想

基本思路是使用两个指针分别从 u 和 v 向上移动，最终在 LCA 处相遇。

关键点：

两个指针必须处于同一深度
然后同时向上移动直到相遇

3.2. 预处理

我们需要先进行一次 DFS 遍历，记录每个节点的深度和父节点：

algorithm DFS(v, Adj, Visited, Depth, Parent):
    Visited[v] <- true
    for u in Adj[v]:
        if not Visited[u]:
            Depth[u] <- Depth[v] + 1
            Parent[u] <- v
            DFS(u, Adj, Visited, Depth, Parent)

预处理复杂度为 O(n)，其中 n 是节点数量。

3.3. 查找 LCA

algorithm NaiveLCA(u, v, Depth, Parent):
    while Depth[u] != Depth[v]:
        if Depth[u] > Depth[v]:
            u <- Parent[u]
        else:
            v <- Parent[v]
    while u != v:
        u <- Parent[u]
        v <- Parent[v]
    return u

算法复杂度为 O(h)，其中 h 是树的高度。在树退化为链表时，复杂度会达到 O(n)。

4. 稀疏表（Sparse Table）背景知识

稀疏表是一种可以快速回答区间查询的数据结构，常用于静态数组的范围最小/最大值查询。

4.1. 构建稀疏表

algorithm BuildSparseTable(Arr, n):
    Log <- ceil(log2(n))
    for i <- 1 to n:
        ST[i, 0] <- Arr[i]
    for j <- 1 to Log:
        for i <- 1 to n - 2^j + 1:
            ST[i, j] <- min(ST[i, j-1], ST[i + 2^(j-1), j-1])

构建复杂度为 O(n log n)

4.2. 使用稀疏表查询

algorithm RangeMinQuery(L, R, ST, N):
    Log <- ceil(log2(N))
    Ans <- infinity
    for j <- Log to 0:
        if L + 2^j - 1 <= R:
            Ans <- min(Ans, ST[L, j])
            L <- L + 2^j
    return Ans

查询复杂度为 O(log n)

5. 二进制跳跃法（Binary Lifting Approach）

5.1. 核心思想

构建一个稀疏表，用于存储每个节点的 2^j 级祖先。

ST[x][j] 表示从 x 节点向上跳 2^j 步后到达的节点
这相当于一个跳跃指针结构

5.2. 预处理

algorithm BuildBinaryLiftingSparseTable(N, Par):
    Log <- ceil(log2(N))
    for i <- 1 to N:
        ST[i, 0] <- Par[i]
    for j <- 1 to Log:
        for i <- 1 to N:
            ST[i, j] <- ST[ST[i, j-1], j-1]

5.3. 查找 LCA 算法

algorithm EfficientLCA(u, v, Depth, ST, N):
    if Depth[u] < Depth[v]:
        swap(u, v)
    Log <- ceil(log2(N))
    Need <- Depth[u] - Depth[v]
    for j <- Log to 0:
        if 2^j <= Need:
            u <- ST[u, j]
            Need <- Need - 2^j
    if u == v:
        return u
    for j <- Log to 0:
        if ST[u, j] != ST[v, j]:
            u <- ST[u, j]
            v <- ST[v, j]
    return ST[u, 0]

算法复杂度为 O(log n)，比暴力法快很多。

5.4. 算法步骤总结

预处理（仅一次）：
- 找到每个节点的深度和父节点 ✅
- 构建稀疏表 ✅
  复杂度：O(n log n)
每次查询 LCA：
- 调整两个节点到同一深度 ✅
- 同时向上跳跃查找 LCA ✅
  复杂度：O(log n)

6. 方法对比

方法	预处理复杂度	单次查询复杂度	空间复杂度	是否需要稀疏表
暴力法	O(n)	O(n)	O(n)	❌
二进制跳跃法	O(n log n)	O(log n)	O(n log n)	✅

✅ 优势：适合处理大量 LCA 查询，预处理一次后每次查询效率高
⚠️ 缺陷：需要额外空间，预处理时间稍长

7. 总结

我们介绍了两种查找树中两个节点最低公共祖先的方法：

暴力法：简单直观，但效率较低，适合少量查询
二进制跳跃法：预处理构建稀疏表，适合大量查询，效率更高

在实际应用中，如果需要频繁查询 LCA，推荐使用二进制跳跃法。

Persistence

REST

Security