基于深度的LCA算法： 对于两个结点u、v，它们的深度分别为depth(u)、depth(v)，对于其公共祖先w，深度为depth(w)，u需要向上回溯depth(u)-depth(w)步，v需要depth(v)-depth(w)步。 因此，只需要u，v中深度较大的向上移，直到 depth(u)=depth(v) && 此时指向一个结点。
因此，求出LCA的时间复杂度为O（depth(u)+depth(v)）； 求深度，只需要进行一次遍历，O(n)。
如果是完全二叉树的话，相当于深度（下标）已经建立好了，直接根据LCA进行计算。
vector<int> G[MAXV]; // 树
int root; int parent[MAXV]; // 父节点； （并查集）
int depth[MAXV]; // 节点深度 // v:当前结点 p:父节点 d：深度
void DFS(int v,int p,int d){
parent[v]=p;
depth[v]=d;
for(auto& p:G[v]){
dfs(p,v,d+);
}
} void init(){
dfs(root,-,);
} int LCA(int u,int v){
while(depth[u]>depth[v]){
u=parent[u];
}
while(depth[u]<depth[v]){
v=parent[v];
}
while(u!=v){
u=parent[u];
v=parent[v];
}
return u;
}
如果需要查找多对LCA，可以考虑二分查找的性质，来找到最小步数。