LCA最近公共祖先问题详解
图论和树结构中最近公共祖先（Least Common Ancestor，LCA）是一个经典的问题，本文我将详细介绍LCA问题的常见求解算法、优化策略，并结合Java代码示例，带你全面掌握这一重要算法问题的求解方法。
一、LCA问题定义
1.1 问题描述
给定一棵有根树 T T T ，对于树中的任意两个节点 u u u 和 v v v ，最近公共祖先指的是在树中同时是 u u u 和 v v v 祖先的节点中距离根节点最远（深度最大）的那个节点 。特别地，如果 u u u 是 v v v 的祖先（或反之），那么 u u u（或 v v v）就是它们的最近公共祖先；如果 u = v u = v u=v ，则 u u u（或 v v v）本身就是自己和自己的最近公共祖先。
例如，在下图所示的树中：
1
/ \
2 3
/ \ / \
4 5 6 7
节点 4 4 4 和 5 5 5 的最近公共祖先是节点 2 2 2；节点 4 4 4 和 7 7 7 的最近公共祖先是节点 1 1 1；节点 6 6 6 和 6 6 6 的最近公共祖先是节点 6 6 6 。
1.2 应用场景
- 数据查询：在数据库的树形存储结构中，通过求解LCA可以快速找到两个数据节点的最近公共分类，用于优化查询操作。
- 网络路由：在计算机网络的树形拓扑结构中，LCA可用于确定两个节点之间通信的最短路径需要经过的关键节点，提高网络传输效率。
- 编译器设计：在语法树中，求解LCA有助于分析代码中不同语法单元之间的关系，辅助进行语法检查和代码优化。
二、常见求解算法
2.1 暴力搜索
思路
从节点 u u u 和 v v v 开始，分别向上遍历它们到根节点的路径，记录路径上的所有节点。然后比较两条路径，找到第一个相同的节点，该节点即为 u u u 和 v v v 的最近公共祖先。
实现步骤
- 分别从节点 u u u 和 v v v 出发，向上遍历树，将经过的节点依次存入两个集合（或列表） p a t h U pathU pathU 和 p a t h V pathV pathV 。
- 从两个集合的末尾开始向前比较，找到第一个相同的节点，该节点就是最近公共祖先。
Java代码示例
import java.util.ArrayList;
import java.util.List;
class TreeNode {
int val;
TreeNode parent;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
public class BruteForceLCA {
public static TreeNode bruteForceLCA(TreeNode u, TreeNode v) {
List<TreeNode> pathU = new ArrayList<>();
List<TreeNode> pathV = new ArrayList<>();
// 构建节点u到根节点的路径
TreeNode current = u;
while (current != null) {
pathU.add(current);
current = current.parent;
}
// 构建节点v到根节点的路径
current = v;
while (current != null) {
pathV.add(current);
current = current.parent;
}
// 从路径末尾开始比较，找到第一个相同节点
int i = pathU.size() - 1;
int j = pathV.size() - 1;
while (i >= 0 && j >= 0 && pathU.get(i) == pathV.get(j)) {
i--;
j--;
}
return pathU.get(i + 1);
}
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
TreeNode node2 = new TreeNode(2);
TreeNode node3 = new TreeNode(3);
TreeNode node4 = new TreeNode(4);
TreeNode node5 = new TreeNode(5);
root.left = node2;
root.right = node3;
node2.left = node4;
node2.right = node5;
node2.parent = root;
node3.parent = root;
node4.parent = node2;
node5.parent = node2;
TreeNode lca = bruteForceLCA(node4, node5);
System.out.println("最近公共祖先的值: " + lca.val);
}
}
步骤简洁:递归优化
核心逻辑：一样属于求解二叉树LCA问题的暴力求解法，但是胜在步骤清晰，过程简洁，通过递归遍历二叉树的左右子树，利用后序遍历的性质判断祖先关系。
- 若当前节点是 p 或 q，直接返回当前节点。
- 若左右子树分别找到 p 和 q，则当前节点为 LCA。
- 否则返回非空的子树结果（说明 p 或 q 在该子树中）。
适用于单次查询，易于理解，但在树高度较大时可能导致栈溢出。
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// 终止条件：当前节点为空，或找到p/q中的一个
if (root == null || root == p || root == q) return root;
// 递归遍历左右子树
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
// 情况1：左右子树都找到目标节点，当前节点为LCA
if (left != null && right != null) return root;
// 情况2：左右子树都没找到目标节点
if (left == null && right == null) return null;
// 情况3：只有左子树或右子树找到目标节点，返回非空的结果
return left == null ? right : left;
}
}
时间与空间复杂度
- 时间复杂度：最坏情况下，需要遍历从 u u u 和 v v v 到根节点的路径，假设树的高度为 h h h ，则时间复杂度为 O ( h ) O(h) O(h) 。对于一般的树， h h h 可能接近节点数 n n n ，所以时间复杂度为 O ( n ) O(n) O(n) 。
- 空间复杂度：需要存储两条路径，最坏情况下路径长度为 h h h ，所以空间复杂度为 O ( h ) O(h) O(h) ，即 O ( n ) O(n) O(n) 。
2.2 倍增算法
思路
倍增算法基于动态规划的思想，利用倍增数组记录每个节点向上跳跃 2 k 2^k 2k 步后的祖先节点。通过预处理构建倍增数组，在查询时，先将深度较大的节点向上调整到与另一个节点相同深度，然后同时向上跳跃，找到最近公共祖先。
实现步骤
- 预处理：
- 定义两个数组：
depth[]记录每个节点的深度，ancestor[i][j]表示节点 i i i 向上跳跃 2 j 2^j 2j 步后的祖先节点。 - 从根节点开始进行深度优先搜索（DFS），初始化
depth[]和ancestor[i][0]（即节点 i i i 的父节点）。 - 利用递推公式
ancestor[i][j] = ancestor[ancestor[i][j - 1]][j - 1]计算其他ancestor[i][j]的值 。
- 定义两个数组：
- 查询：
- 首先将深度较大的节点向上调整到与另一个节点相同深度。
- 然后从最大的跳跃步长开始，同时向上跳跃两个节点，直到找到最近公共祖先。
Java代码示例
import java.util.ArrayList;
import java.util.List;
class TreeNode {
int val;
List<TreeNode> children;
TreeNode(int val) {
this.val = val;
children = new ArrayList<>();
}
}
public class DoublingLCA {
private static int MAX_LOG = 20;
private static int[] depth;
private static TreeNode[][] ancestor;
// 预处理函数，计算深度和倍增数组
private static void dfs(TreeNode node, TreeNode parent, int d) {
depth[node.val] = d;
ancestor[node.val][0] = parent;
for (TreeNode child : node.children) {
if (child != parent) {
dfs(child, node, d + 1);
}
}
}
private static void preprocess(TreeNode root) {
depth = new int[10001];
ancestor = new TreeNode[10001][MAX_LOG];
dfs(root, null, 0);
for (int j = 1; j < MAX_LOG; j++) {
for (int i = 1; i <= 10000; i++) {
if (ancestor[i][j - 1] != null) {
ancestor[i][j] = ancestor[ancestor[i][j - 1]][j - 1];
}
}
}
}
// 查询函数，计算最近公共祖先
public static TreeNode query(TreeNode u, TreeNode v) {
if (depth[u.val] < depth[v.val]) {
TreeNode temp = u;
u = v;
v = temp;
}
int diff = depth[u.val] - depth[v.val];
for (int i = 0; i < MAX_LOG; i++) {
if ((diff & (1 << i)) != 0) {
u = ancestor[u.val][i];
}
}
if (u == v) {
return u;
}
for (int i = MAX_LOG - 1; i >= 0; i--) {
if (ancestor[u.val][i] != null && ancestor[u.val][i] != ancestor[v.val][i]) {
u = ancestor[u.val][i];
v = ancestor[v.val][i];
}
}
return ancestor[u.val][0];
}
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
TreeNode node2 = new TreeNode(2);
TreeNode node3 = new TreeNode(3);
TreeNode node4 = new TreeNode(4);
TreeNode node5 = new TreeNode(5);
root.children.add(node2);
root.children.add(node3);
node2.children.add(node4);
node2.children.add(node5);
preprocess(root);
TreeNode lca = query(node4, node5);
System.out.println("最近公共祖先的值: " + lca.val);
}
}
时间与空间复杂度
- 时间复杂度：预处理阶段，深度优先搜索时间复杂度为 O ( n ) O(n) O(n) ，计算倍增数组时间复杂度为 O ( n log n ) O(n \log n) O(nlogn) ；查询阶段，每次查询时间复杂度为 O ( log n ) O(\log n) O(logn) 。总体而言，预处理时间复杂度为 O ( n log n ) O(n \log n) O(nlogn) ，单次查询时间复杂度为 O ( log n ) O(\log n) O(logn) 。
- 空间复杂度：需要存储深度数组和倍增数组，空间复杂度为 O ( n log n ) O(n \log n) O(nlogn) 。
2.3 Tarjan算法（离线算法）
思路
Tarjan算法是一种离线算法（即需要提前知道所有查询），基于并查集和深度优先搜索实现。在深度优先搜索过程中，对于每个访问到的节点，将其所在集合合并到父节点所在集合，并标记已访问。当处理完一个节点的所有子树后，对于针对该节点的所有查询，检查另一个查询节点是否已访问，若已访问，则它们的最近公共祖先就是另一个查询节点所在集合的根节点。
实现步骤
- 初始化并查集，每个节点自成一个集合。
- 从根节点开始进行深度优先搜索，对于当前节点 u u u ：
- 标记 u u u 已访问。
- 递归处理 u u u 的所有子树。
- 将 u u u 所在集合合并到其父节点所在集合。
- 处理针对 u u u 的所有查询，若另一个查询节点 v v v 已访问，则 L C A ( u , v ) LCA(u, v) LCA(u,v) 为 v v v 所在集合的根节点。
Java代码示例
import java.util.ArrayList;
import java.util.List;
class TreeNode {
int val;
List<TreeNode> children;
TreeNode(int val) {
this.val = val;
children = new ArrayList<>();
}
}
class Query {
int node1;
int node2;
int index;
Query(int node1, int node2, int index) {
this.node1 = node1;
this.node2 = node2;
this.index = index;
}
}
public class TarjanLCA {
private static int[] parent;
private static boolean[] visited;
private static int[] result;
private static int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
private static void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
parent[rootY] = rootX;
}
}
private static void tarjan(TreeNode node, List<Query>[] queries) {
visited[node.val] = true;
for (TreeNode child : node.children) {
if (!visited[child.val]) {
tarjan(child, queries);
union(node.val, child.val);
}
}
for (Query query : queries[node.val]) {
if (visited[query.node2]) {
result[query.index] = find(query.node2);
}
}
}
public static int[] solve(TreeNode root, List<Query> queries) {
int n = 10001;
parent = new int[n];
visited = new boolean[n];
result = new int[queries.size()];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
@SuppressWarnings("unchecked")
List<Query>[] queryLists = new ArrayList[n];
for (int i = 0; i < n; i++) {
queryLists[i] = new ArrayList<>();
}
for (int i = 0; i < queries.size(); i++) {
Query query = queries.get(i);
queryLists[query.node1].add(query);
queryLists[query.node2].add(new Query(query.node2, query.node1, i));
}
tarjan(root, queryLists);
return result;
}
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
TreeNode node2 = new TreeNode(2);
TreeNode node3 = new TreeNode(3);
TreeNode node4 = new TreeNode(4);
TreeNode node5 = new TreeNode(5);
root.children.add(node2);
root.children.add(node3);
node2.children.add(node4);
node2.children.add(node5);
List<Query> queries = new ArrayList<>();
queries.add(new Query(4, 5, 0));
int[] lcaResults = solve(root, queries);
System.out.println("最近公共祖先的值: " + lcaResults[0]);
}
}
时间与空间复杂度
- 时间复杂度：深度优先搜索时间复杂度为 O ( n + m ) O(n + m) O(n+m) ，其中 n n n 是节点数， m m m 是查询数；并查集操作时间复杂度为 O ( ( n + m ) α ( n ) ) O((n + m) \alpha(n)) O((n+m)α(n)) ， α ( n ) \alpha(n) α(n) 是阿克曼函数的反函数，增长极其缓慢，可近似看作常数。总体时间复杂度为 O ( n + m ) O(n + m) O(n+m) 。
- 空间复杂度：需要存储并查集、访问标记数组、结果数组以及查询列表，空间复杂度为 O ( n + m ) O(n + m) O(n+m) 。
三、算法优化与拓展
3.1 优化方向
- 减少空间占用：对于倍增算法，可以通过压缩存储方式，减少倍增数组的空间占用；对于Tarjan算法，可优化并查集的实现，进一步降低空间复杂度。
- 提高查询效率：在处理大量查询时，可以对算法进行并行化改造，利用多核处理器提高查询速度；对于在线算法，还可以采用缓存机制，存储最近查询的结果，减少重复计算。
3.2 拓展问题
- 动态LCA问题：在树结构动态变化（如节点插入、删除）的情况下，如何高效地维护最近公共祖先信息。
- 多源LCA问题：给定多个节点，求它们的最近公共祖先，这在一些复杂的数据结构和应用场景中具有重要意义。
总结
本文我介绍了暴力搜索、倍增算法和Tarjan算法三种常见的求解方法，每种算法都有适用场景，暴力搜索算法简单直观，适用于小规模数据；倍增算法是高效的在线算法，适合多次查询；Tarjan算法作为离线算法，在批量处理查询时表现出色。
That’s all, thanks for reading!
觉得有用就点个赞、收进收藏夹吧！关注我，获取更多干货～