LCA最近公共祖先问题详解

图论和树结构中最近公共祖先（Least Common Ancestor，LCA）是一个经典的问题，本文我将详细介绍LCA问题的常见求解算法、优化策略，并结合Java代码示例，带你全面掌握这一重要算法问题的求解方法。

一、LCA问题定义

1.1 问题描述

给定一棵有根树 $T$ ，对于树中的任意两个节点 $u$ 和 $v$ ，最近公共祖先指的是在树中同时是 $u$ 和 $v$ 祖先的节点中距离根节点最远（深度最大）的那个节点 。特别地，如果 $u$ 是 $v$ 的祖先（或反之），那么 $u$（或 $v$）就是它们的最近公共祖先；如果 $u=v$ ，则 $u$（或 $v$）本身就是自己和自己的最近公共祖先。

例如，在下图所示的树中：

        1/   \2     3/ \   / \4   5 6   7

节点 $4$ 和 $5$ 的最近公共祖先是节点 $2$；节点 $4$ 和 $7$ 的最近公共祖先是节点 $1$；节点 $6$ 和 $6$ 的最近公共祖先是节点 $6$ 。

1.2 应用场景

• 数据查询：在数据库的树形存储结构中，通过求解LCA可以快速找到两个数据节点的最近公共分类，用于优化查询操作。
• 网络路由：在计算机网络的树形拓扑结构中，LCA可用于确定两个节点之间通信的最短路径需要经过的关键节点，提高网络传输效率。
• 编译器设计：在语法树中，求解LCA有助于分析代码中不同语法单元之间的关系，辅助进行语法检查和代码优化。

二、常见求解算法

2.1 暴力搜索

思路

从节点 $u$ 和 $v$ 开始，分别向上遍历它们到根节点的路径，记录路径上的所有节点。然后比较两条路径，找到第一个相同的节点，该节点即为 $u$ 和 $v$ 的最近公共祖先。

实现步骤

1. 分别从节点 $u$ 和 $v$ 出发，向上遍历树，将经过的节点依次存入两个集合（或列表）$pathU$ 和 $pathV$ 。
2. 从两个集合的末尾开始向前比较，找到第一个相同的节点，该节点就是最近公共祖先。

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问题的暴力求解法，但是胜在步骤清晰，过程简洁，通过递归遍历二叉树的左右子树，利用后序遍历的性质判断祖先关系。

1. 若当前节点是 p 或 q，直接返回当前节点。
2. 若左右子树分别找到 p 和 q，则当前节点为 LCA。
3. 否则返回非空的子树结果（说明 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：左右子树都找到目标节点，当前节点为LCAif (left != null && right != null) return root;// 情况2：左右子树都没找到目标节点if (left == null && right == null) return null;// 情况3：只有左子树或右子树找到目标节点，返回非空的结果return left == null ? right : left;}
}

时间与空间复杂度

• 时间复杂度：最坏情况下，需要遍历从 $u$ 和 $v$ 到根节点的路径，假设树的高度为 $h$ ，则时间复杂度为 $O(h)$ 。对于一般的树，$h$ 可能接近节点数 $n$ ，所以时间复杂度为 $O(n)$ 。
• 空间复杂度：需要存储两条路径，最坏情况下路径长度为 $h$ ，所以空间复杂度为 $O(h)$ ，即 $O(n)$ 。

2.2 倍增算法

思路

倍增算法基于动态规划的思想，利用倍增数组记录每个节点向上跳跃 $2^k$ 步后的祖先节点。通过预处理构建倍增数组，在查询时，先将深度较大的节点向上调整到与另一个节点相同深度，然后同时向上跳跃，找到最近公共祖先。

实现步骤

1. 预处理：
   • 定义两个数组：depth[] 记录每个节点的深度，ancestor[i][j] 表示节点 $i$ 向上跳跃 $2^j$ 步后的祖先节点。
   • 从根节点开始进行深度优先搜索（DFS），初始化 depth[] 和 ancestor[i][0]（即节点 $i$ 的父节点）。
   • 利用递推公式 ancestor[i][j] = ancestor[ancestor[i][j - 1]][j - 1] 计算其他 ancestor[i][j] 的值 。
2. 查询：
   • 首先将深度较大的节点向上调整到与另一个节点相同深度。
   • 然后从最大的跳跃步长开始，同时向上跳跃两个节点，直到找到最近公共祖先。

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\log n)$ ；查询阶段，每次查询时间复杂度为 $O(\log n)$ 。总体而言，预处理时间复杂度为 $O(n\log n)$ ，单次查询时间复杂度为 $O(\log n)$ 。
• 空间复杂度：需要存储深度数组和倍增数组，空间复杂度为 $O(n\log n)$ 。

2.3 Tarjan算法（离线算法）

思路

Tarjan算法是一种离线算法（即需要提前知道所有查询），基于并查集和深度优先搜索实现。在深度优先搜索过程中，对于每个访问到的节点，将其所在集合合并到父节点所在集合，并标记已访问。当处理完一个节点的所有子树后，对于针对该节点的所有查询，检查另一个查询节点是否已访问，若已访问，则它们的最近公共祖先就是另一个查询节点所在集合的根节点。

实现步骤

1. 初始化并查集，每个节点自成一个集合。
2. 从根节点开始进行深度优先搜索，对于当前节点 $u$ ：
   • 标记 $u$ 已访问。
   • 递归处理 $u$ 的所有子树。
   • 将 $u$ 所在集合合并到其父节点所在集合。
   • 处理针对 $u$ 的所有查询，若另一个查询节点 $v$ 已访问，则 $LCA(u,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)$ ，其中 $n$ 是节点数，$m$ 是查询数；并查集操作时间复杂度为 $O((n+m)\alpha (n))$ ，$\alpha (n)$ 是阿克曼函数的反函数，增长极其缓慢，可近似看作常数。总体时间复杂度为 $O(n+m)$ 。
• 空间复杂度：需要存储并查集、访问标记数组、结果数组以及查询列表，空间复杂度为 $O(n+m)$ 。

三、算法优化与拓展

3.1 优化方向

• 减少空间占用：对于倍增算法，可以通过压缩存储方式，减少倍增数组的空间占用；对于Tarjan算法，可优化并查集的实现，进一步降低空间复杂度。
• 提高查询效率：在处理大量查询时，可以对算法进行并行化改造，利用多核处理器提高查询速度；对于在线算法，还可以采用缓存机制，存储最近查询的结果，减少重复计算。

3.2 拓展问题

• 动态LCA问题：在树结构动态变化（如节点插入、删除）的情况下，如何高效地维护最近公共祖先信息。
• 多源LCA问题：给定多个节点，求它们的最近公共祖先，这在一些复杂的数据结构和应用场景中具有重要意义。

总结

本文我介绍了暴力搜索、倍增算法和Tarjan算法三种常见的求解方法，每种算法都有适用场景，暴力搜索算法简单直观，适用于小规模数据；倍增算法是高效的在线算法，适合多次查询；Tarjan算法作为离线算法，在批量处理查询时表现出色。

That’s all, thanks for reading!
觉得有用就点个赞、收进收藏夹吧！关注我，获取更多干货～