最近公共祖先（Lowest Common Ancestor，LCA）是指两个或多个节点在一棵树中共有的祖先节点中深度最低的那个。在算法竞赛中，LCA是一种常用的问题，在树上进行相关操作的时候，LCA可以有效提高算法的效率。
一、基本概念
在树中，从根节点向下走到节点$p$和$q$，假设它们之间任意一条路径上的最后一个公共节点为$x$，则$x$是$p$和$q$的公共祖先。如果一个节点是它自己的祖先，那么它就是公共祖先中深度最低的那个，也就是最近公共祖先。
二、求解LCA的方法
1.暴力枚举法
暴力枚举算法的做法是，对于每一对需要查找LCA的节点$p$和$q$，从$p$依次向上遍历祖先，直到找到某个祖先节点$u$，使得$u$是$q$的祖先。这样，找到的节点$u$就是$p$和$q$的最近公共祖先。这种算法的时间复杂度为$O(n^2)$。
struct TreeNode{
int val;
TreeNode* left;
TreeNode* right;
};
using p = pair;
TreeNode* LCA(TreeNode* root, TreeNode* p, TreeNode* q){
function isAncestor = [](TreeNode* p, TreeNode* q){
if(p == nullptr) return false;
if(p == q) return true;
return isAncestor(p->left, q) || isAncestor(p->right, q);
};
queue q; q.push({root, -1}); vector
tmp; while(!q.empty()){ int n = q.size(); while(n--){ auto [cur, parent] = q.front(); q.pop(); tmp.emplace_back(cur, parent); if(cur->val == p->val || cur->val == q->val){ if(tmp.size() == 1) return cur; break; } if(cur->left){ q.push({cur->left, cur->val}); } if(cur->right){ q.push({cur->right, cur->val}); } } if(isAncestor(tmp.back().first, p) && isAncestor(tmp.back().first, q)) continue; while(tmp.size()){ auto [cur, _] = tmp.back(); tmp.pop_back(); if(isAncestor(cur, p) && isAncestor(cur, q)) return cur; } } return nullptr;}
2. 深度优先搜索法
在对树进行深度优先搜索（DFS）的时候，记录下每个节点的深度和父节点，如果需要查找节点$p$和$q$的LCA，对于节点$p$和$q$，沿着树分别向上找到它们的祖先节点，一直找到它们的深度相等，这样的节点就是它们的最近公共祖先。
// 建立 parent 和 depth 数组
void dfs(int u, int p, int d){
parent[u] = p;
depth[u] = d;
for(auto v : g[u]){
if(v != p){
dfs(v, u, d + 1);
}
}
}
// 求解LCA
int LCA(int u, int v){
int du = depth[u];
int dv = depth[v];
while(du > dv){
u = parent[u];
du--;
}
while(dv > du){
v = parent[v];
dv--;
}
while(u != v){
u = parent[u];
v = parent[v];
}
return u;
}
3.倍增法
针对较大规模的树，在求解LCA时暴力枚举的时间复杂度太高，可采用倍增法。倍增法的思路是，预处理出每个节点往上跳$2^k$个节点后能到达的节点，从而减少查找LCA的时间复杂度，使之变为$O(logn)$。具体实现时，需要预处理一个$fa[i][j]$数组，表示从节点$i$开始往上跳$2^j$个节点所能到达的节点编号。同时，还需要预处理一个$depth[i]$数组，表示节点$i$的深度。
// 节点编号从`0`开始
const int MAXN = 1e5 + 10;
int depth[MAXN], fa[MAXN][21];
// 预处理深度和预处理fa数组
void dfs(int u, int p, int d){
depth[u] = d;
fa[u][0] = p;
for(int i = 1; (1 << i) < MAXN; ++i){
fa[u][i] = fa[fa[u][i - 1]][i - 1];
}
for(auto v : g[u]){
if(v != p){
dfs(v, u, d + 1);
}
}
}
// 求解LCA
int LCA(int u, int v){
if(depth[u] = 0; --i){
if(depth[u] - (1 <= depth[v]){
u = fa[u][i];
}
}
if(u == v) return u;
for(int i = log2(depth[u]); i >= 0; --i){
if(fa[u][i] != fa[v][i]){
u = fa[u][i];
v = fa[v][i];
}
}
return fa[u][0];
}
三、总结
求解树上两个节点的最近公共祖先是树相关算法中的重要问题。根据不同的应用场景和需求，可以选择不同的LCA算法，如暴力枚举、深度优先搜索和倍增法等。在实际应用中，需要根据数据规模和时间复杂度的要求，选择合适的算法。
原创文章，作者：RZPJY，如若转载，请注明出处：https://www.506064.com/n/368565.html
微信扫一扫 
支付宝扫一扫 