最近公共祖先（Lowest Common Ancestor，简称LCA）是树结构算法中的核心问题。给定一棵有根树和两个节点，求它们深度最大的公共祖先。LCA问题在文件系统路径解析、生物进化树分析、社交网络关系计算、游戏技能树导航等领域都有重要应用。
问题定义
在一棵有根树中，节点 u 和节点 v 的最近公共祖先是指同时是 u 和 v 的祖先且深度最大的节点。特别地，一个节点可以是它自己的祖先。
方法一：倍增法（在线查询，O(n log n)预处理 + O(log n)查询）
核心思路
预处理每个节点的 2^k 级祖先，存储在 up[k][u] 数组中。查询时，先将两个节点提升到同一深度，然后同时向上跳跃，直到找到公共祖先。
预处理公式：
up[k][u] = up[k-1][up[k-1][u]]
即节点u的2^k级祖先 = u的2^(k-1)级祖先的2^(k-1)级祖先。
Java实现
import java.util.*;
public class LCABinaryLifting {
private int n; // 节点数
private int maxLog; // 最大跳跃层数
private List<Integer>[] tree; // 邻接表
private int[][] up; // up[k][v]表示v的2^k级祖先
private int[] depth; // 节点深度
/**
* 初始化LCA结构
* @param n 节点数（节点编号从1到n）
*/
@SuppressWarnings("unchecked")
public LCABinaryLifting(int n) {
this.n = n;
this.maxLog = (int) (Math.log(n) / Math.log(2)) + 1;
this.tree = new ArrayList[n + 1];
this.up = new int[maxLog][n + 1];
this.depth = new int[n + 1];
for (int i = 0; i <= n; i++) {
tree[i] = new ArrayList<>();
}
}
/**
* 添加无向边
*/
public void addEdge(int u, int v) {
tree[u].add(v);
tree[v].add(u);
}
/**
* 从根节点开始预处理祖先信息
* @param root 根节点
*/
public void preprocess(int root) {
// 使用BFS或DFS填充up表和depth数组
dfs(root, 0);
// 动态规划填充倍增表
for (int k = 1; k < maxLog; k++) {
for (int v = 1; v <= n; v++) {
int midAncestor = up[k - 1][v];
up[k][v] = midAncestor == 0 ? 0 : up[k - 1][midAncestor];
}
}
}
private void dfs(int u, int parent) {
up[0][u] = parent; // 直接祖先
depth[u] = depth[parent] + 1;
for (int v : tree[u]) {
if (v != parent) {
dfs(v, u);
}
}
}
/**
* 查询u和v的最近公共祖先
* @param u 节点u
* @param v 节点v
* @return LCA节点
*/
public int query(int u, int v) {
// 确保u是较深的节点
if (depth[u] < depth[v]) {
int temp = u;
u = v;
v = temp;
}
// 将u提升到与v同一深度
int diff = depth[u] - depth[v];
for (int k = maxLog - 1; k >= 0; k--) {
if ((diff & (1 << k)) != 0) {
u = up[k][u];
}
}
// 如果v就是u的祖先
if (u == v) {
return u;
}
// 同时向上跳跃
for (int k = maxLog - 1; k >= 0; k--) {
if (up[k][u] != up[k][v]) {
u = up[k][u];
v = up[k][v];
}
}
// 此时u和v的直接祖先就是LCA
return up[0][u];
}
/**
* 获取两个节点之间的距离（边数）
*/
public int distance(int u, int v) {
int lca = query(u, v);
return depth[u] + depth[v] - 2 * depth[lca];
}
public static void main(String[] args) {
// 构建示例树
// 1
// / | \
// 2 3 4
// / \ |
// 5 6 7
LCABinaryLifting lca = new LCABinaryLifting(7);
lca.addEdge(1, 2);
lca.addEdge(1, 3);
lca.addEdge(1, 4);
lca.addEdge(2, 5);
lca.addEdge(2, 6);
lca.addEdge(4, 7);
lca.preprocess(1);
System.out.println("LCA(5, 6) = " + lca.query(5, 6)); // 2
System.out.println("LCA(5, 7) = " + lca.query(5, 7)); // 1
System.out.println("LCA(5, 2) = " + lca.query(5, 2)); // 2
System.out.println("LCA(3, 7) = " + lca.query(3, 7)); // 1
System.out.println("Distance(5, 7) = " + lca.distance(5, 7)); // 4
}
}
方法二：Tarjan离线算法（O(n + q) α(n)）
核心思路
Tarjan算法利用并查集（Union-Find）在深度优先搜索过程中回答所有查询。其核心思想是：当访问完一个节点的所有子树后，将该节点与子树的根合并到同一集合，并记录该集合的”代表”为当前节点。此时，所有以该节点为LCA的查询都可以被回答。
Java实现
import java.util.*;
public class LCATarjan {
private int n;
private List<Integer>[] tree;
private List<int[]>[] queries; // 存储每个节点相关的查询
private int[] answer;
private boolean[] visited;
private int[] parent;
private int[] ancestor; // 并查集的"代表"祖先
@SuppressWarnings("unchecked")
public LCATarjan(int n, int queryCount) {
this.n = n;
this.tree = new ArrayList[n + 1];
this.queries = new ArrayList[n + 1];
this.answer = new int[queryCount];
this.visited = new boolean[n + 1];
this.parent = new int[n + 1];
this.ancestor = new int[n + 1];
for (int i = 0; i <= n; i++) {
tree[i] = new ArrayList<>();
queries[i] = new ArrayList<>();
parent[i] = i;
}
}
public void addEdge(int u, int v) {
tree[u].add(v);
tree[v].add(u);
}
/**
* 添加查询，记录查询编号
* @param u 节点u
* @param v 节点v
* @param idx 查询编号
*/
public void addQuery(int u, int v, int idx) {
queries[u].add(new int[]{v, idx});
queries[v].add(new int[]{u, idx});
}
/**
* 执行Tarjan离线LCA算法
* @param root 根节点
*/
public void solve(int root) {
tarjanDFS(root);
}
private void tarjanDFS(int u) {
visited[u] = true;
ancestor[u] = u; // 初始时自己是自己的祖先代表
for (int v : tree[u]) {
if (!visited[v]) {
tarjanDFS(v);
union(u, v); // 将子树合并到当前节点
ancestor[find(u)] = u; // 更新合并后的代表祖先
}
}
// 处理所有与u相关的查询
for (int[] q : queries[u]) {
int v = q[0];
int idx = q[1];
if (visited[v]) {
answer[idx] = ancestor[find(v)];
}
}
}
private int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
private void union(int x, int y) {
int fx = find(x);
int fy = find(y);
if (fx != fy) {
parent[fx] = fy;
}
}
public int getAnswer(int idx) {
return answer[idx];
}
public static void main(String[] args) {
// 构建示例树
// 1
// / | \
// 2 3 4
// / \ |
// 5 6 7
int queryCount = 4;
LCATarjan lca = new LCATarjan(7, queryCount);
lca.addEdge(1, 2);
lca.addEdge(1, 3);
lca.addEdge(1, 4);
lca.addEdge(2, 5);
lca.addEdge(2, 6);
lca.addEdge(4, 7);
// 添加查询
lca.addQuery(5, 6, 0); // LCA = 2
lca.addQuery(5, 7, 1); // LCA = 1
lca.addQuery(5, 2, 2); // LCA = 2
lca.addQuery(3, 7, 3); // LCA = 1
lca.solve(1);
System.out.println("LCA(5, 6) = " + lca.getAnswer(0));
System.out.println("LCA(5, 7) = " + lca.getAnswer(1));
System.out.println("LCA(5, 2) = " + lca.getAnswer(2));
System.out.println("LCA(3, 7) = " + lca.getAnswer(3));
}
}
两种方法的对比
| 特性 | 倍增法 | Tarjan离线算法 |
|---|---|---|
| 预处理时间 | O(n log n) | O(n α(n)) |
| 单次查询时间 | O(log n) | O(1)（均摊） |
| 空间复杂度 | O(n log n) | O(n + q) |
| 查询模式 | 在线（实时查询） | 离线（需预先知道所有查询） |
| 适用场景 | 动态查询、交互式应用 | 批量查询、竞赛编程 |
扩展应用：树上路径问题
路径节点权值和查询
结合LCA和前缀和，可以在O(log n)时间内查询树上任意两节点之间路径的权值和。
public class TreePathQuery {
private LCABinaryLifting lca;
private long[] prefixSum; // 根到节点的权值前缀和
public TreePathQuery(int n, int[] nodeValues) {
this.lca = new LCABinaryLifting(n);
this.prefixSum = new long[n + 1];
// 初始化前缀和需要在构建树后执行DFS
}
/**
* 查询u到v路径上的权值和
*/
public long pathSum(int u, int v) {
int ancestor = lca.query(u, v);
return prefixSum[u] + prefixSum[v] - 2 * prefixSum[ancestor] + nodeValue(ancestor);
}
private int nodeValue(int u) {
// 返回节点u的权值
return 0; // 占位
}
}
复杂度分析
倍增法：
– 预处理：O(n log n) 时间，O(n log n) 空间
– 单次查询：O(log n) 时间
Tarjan算法：
– 总时间：O((n + q) α(n))，其中α为反阿克曼函数，可视为常数
– 空间：O(n + q)
总结
最近公共祖先问题是树算法的基石。倍增法以空间换时间，支持在线查询，适合交互式场景；Tarjan算法通过并查集实现近乎线性的离线处理，适合批量查询场景。掌握这两种方法，能够高效解决绝大多数树上路径、距离和关系类问题。
