最近公共祖先（LeastCommonAncestors，LCA）问题详解问题描述与分析
求有根树的任意两个节点的最近公共祖先。
举个例⼦，如针对下图所⽰的⼀棵普通的⼆叉树来讲：
结点3和结点4的最近公共祖先是结点2，即LCA（3，4）=2 。在此，需要注意到当两个结点在同⼀棵⼦树
上的情况，如结点3和结点2的最近公共祖先为2，即 LCA（3，2）=2。同理：LCA（5，6）=4，LCA（6，10）=1。
明确了题意，咱们便来试着解决这个问题。直观的做法，可能是针对是否为⼆叉查树分情况讨论，这也是⼀般⼈最先想到的思路。除此之外，还有所谓的Tarjan算法、倍增算法、以及转换为RMQ问题（求某段区间的极值）。后⾯这⼏种算法相对⾼级，不那么直观，但思路⽐较有启发性，了解⼀下也有裨益。
解法⼀：暴⼒对待
1.1、是⼆叉查树
在当这棵树是⼆叉查树的情况下，如下图：
那么从树根开始：
如果当前结点t ⼤于结点u、v，说明u、v都在t 的左侧，所以它们的共同祖先必定在t 的左⼦树中，故从t 的左⼦树中继续查；
如果当前结点t ⼩于结点u、v，说明u、v都在t 的右侧，所以它们的共同祖先必定在t 的右⼦树中，故从t 的右⼦树中继续查；
如果当前结点t 满⾜ u <t < v，说明u和v分居在t 的两侧，故当前结点t 即为最近公共祖先；
⽽如果u是v的祖先，那么返回u的⽗结点，同理，如果v是u的祖先，那么返回v的⽗结点。
代码如下所⽰：
public int query(Node t, Node u, Node v) {
int left = u.value;
int right = v.value;
//⼆叉查树内，如果左结点⼤于右结点，不对，交换
if (left > right) {
int temp = left;
left = right;
right = temp;
}
while (true) {
//如果t⼩于u、v，往t的右⼦树中查
if (t.value < left) {
t = t.right;
//如果t⼤于u、v，往t的左⼦树中查
} else if (t.value > right) {
t = t.left;
} else {
return t.value;
}
}
}
1.2、不是⼆叉查树
但如果这棵树不是⼆叉查树，只是⼀棵普通的⼆叉树呢？如果每个结点都有⼀个指针指向它的⽗结点，于是我们可以从任何⼀个结点出发，得到⼀个到达树根结点的单向链表。因此这个问题转换为两个单向链表的第⼀个公共结点。
此外，如果给出根节点，LCA问题可以⽤递归很快解决。⽽关于树的问题⼀般都可以转换为递归（因为树本来就是递归描述），参考代码如下：
node* getLCA(node* root, node* node1, node* node2)
{
if(root == null)
return null;
if(root== node1 || root==node2)
return root;
node* left = getLCA(root->left, node1, node2);
node* right = getLCA(root->right, node1, node2);
// node1 和 node2 不存在祖先关系
if(left != null && right != null)
return root;
/
/ node1 和 node2 其中⼀个是另⼀个的祖先
else if(left != null)
return left;
else if (right != null)
return right;
else
return null;
}
不论是针对普通的⼆叉树，还是针对⼆叉查树，上⾯的解法有⼀个很⼤的弊端就是：如需N 次查询，则总体复杂度会扩⼤N 倍，故这种暴⼒解法仅适合⼀次查询，不适合多次查询。
接下来的解法，将不再区别对待是否为⼆叉查树，⽽是⼀致当做是⼀棵普通的⼆叉树。总体来说，由于可以把LCA问题看成是询问式的，即给出⼀系列询问，程序对每⼀个询问尽快做出反应。故处理这类
问题⼀般有两种解决⽅法：
⼀种是在线算法，相当于循序渐进处理；
另外⼀种则是离线算法，如Tarjan算法，相当于⼀次性批量处理，⼀开始就知道了全部查询，只待询问。
解法⼆：Tarjan算法
如上⽂末节所述，不论咱们所⾯对的⼆叉树是⼆叉查树，或不是⼆叉查树，都可以把求任意两个结点的最近公共祖先，当做是查询的问题，如果是只求⼀次，则是单次查询；如果要求多个任意两个结点的最近公共祖先，则相当于是批量查询。
涉及到批量查询的时候，咱们可以借鉴离线处理的⽅式，这就引出了解决此LCA问题的Tarjan离线算法。
2.1、什么是Tarjan算法
Tarjan算法 （以发现者Robert Tarjan命名）是⼀个在图中寻强连通分量的算法。算法的基本思想为：任选⼀结点开始进⾏深度优先搜索dfs（若深度优先搜索结束后仍有未访问的结点，则再从中任选⼀点再次进⾏）。搜索过程中已访问的结点不再访问。搜索树的若⼲⼦树构成了图的强连通分量。
应⽤到咱们要解决的LCA问题上，则是：对于新搜索到的⼀个结点u，先创建由u构成的集合，再对u的每颗⼦树进⾏搜索，每搜索完⼀棵⼦树，这时候⼦树中所有的结点的最近公共祖先就是u了。
举⼀个例⼦，如下图（不同颜⾊的结点相当于不同的集合）：
假设遍历完10的孩⼦，要处理关于10的请求了，取根节点到当前正在遍历的节点的路径为关键路径，即1-3-8-10，集合的祖先便是关键路径上距离集合最近的点。
⽐如：
1，2，5，6为⼀个集合，祖先为1，集合中点和10的LCA为1
3，7为⼀个集合，祖先为3，集合中点和10的LCA为3
8，9，11为⼀个集合，祖先为8，集合中点和10的LCA为8
10，12为⼀个集合，祖先为10，集合中点和10的LCA为10
得出的结论便是：LCA(u,v)便是根⾄u的路径上到节点v最近的点。
2.2、Tarjan算法如何⽽来
但关键是 Tarjan算法是怎么想出来的呢？再给定下图，你是否能看出来：分别从结点1的左右⼦树当中，任取⼀个结点，设为u、v，这两个任意结点u、v的最近公共祖先都为1。
于此，我们可以得知：若两个结点u、v分别分布于某节点t 的左右⼦树，那么此节点 t即为u和v的最近公共祖先。更进⼀步，考虑到⼀个节点⾃⼰就是LCA的情况，得知：
若某结点t 是两结点u、v的祖先之⼀，且这两结点并不分布于该结点t 的⼀棵⼦树中，⽽是分别在结点t 的左⼦树、右⼦树中，那么该结点t 即为两结点u、v的最近公共祖先。
这个定理就是Tarjan算法的基础。
⼀如上⽂1.1节我们得到的结论：“如果当前结点t 满⾜ u <t < v，说明u和v分居在t 的两侧，故当前结点t 即为最近公共祖先”。
⽽对于本节开头我们所说的“如果要求多个任意两个结点的最近公共祖先，则相当于是批量查询”，即在很多组的询问的情况下，或许可以先确定⼀个LCA。例如是根节点1，然后再去检查所有询问，看是否满⾜刚才的定理，不满⾜就忽视，满⾜就赋值，全部弄完，再去假设2号节点是LCA，再去访问⼀遍。
可此⽅法需要判断⼀个结点是在左⼦树、还是右⼦树，或是都不在，都只能遍历⼀棵树，⽽多次遍历的代价实在是太⼤了，所以我们需要到更好的⽅法。这就引出了下⾯要阐述的Tarjan算法，即每个结点只遍历⼀次，怎么做到的呢，请看下⽂讲解。
2.3、Tarjan算法流程
Tarjan算法流程为：
Procedure dfs（u）；
begin
设置u号节点的祖先为u
若u的左⼦树不为空，dfs（u - 左⼦树）；
若u的右⼦树不为空，dfs（u - 右⼦树）；
访问每⼀条与u相关的询问u、v
-若v已经被访问过，则输出v当前的祖先t（t即u,v的LCA）
标记u为已经访问，将所有u的孩⼦包括u本⾝的祖先改为u的⽗亲
end
普通的dfs 不能直接解决LCA问题，故Tarjan算法的原理是dfs +  ，它每次把两个结点对的最近公共祖先
的查询保存起来，然后dfs 更新⼀次。如此，利⽤并查集优越的时空复杂度，此算法的时间复杂度可以缩⼩⾄O(n＋Q)，其中，n为数据规模，Q为询问个数。
2.4、Tarjan算法C++实现⽰例
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <cstring>
using namespace std;
using namespace std;
struct Node
{
int val;
vector<int> chlidren;
Node(int v):val(v) {}cstring转为int
};
class UnSet
{
public:
int *father;
UnSet(int n): capacity(n)
{
father = new int[n];
for (int i = 0; i < n ;i++)
father[i] = i;
}
~UnSet()
{
delete[] father;
}
int find(int i)
{
return (father[i] == i) ? i : (father[i] = find(father[i]));
}
void unionSet(int a, int b)
{
a = find(a);
b = find(b);
father[b] = a;
}
int size()
{
return capacity;
}
private:
int capacity;
};
class LCA
{
public:
LCA(Node tree[], int n): fatSet(n) //root is tree[0]
{
hasVisit = new bool[n];
memset(hasVisit, false, n * sizeof(bool));
this->tree = tree;
}
map<pair<int, int>, int> calLCA(vector<pair<int, int> >& query)    {
map<int, set<int> > queryMap;
map<pair<int, int>, int> result;
for (int i =0; i< query.size(); i++)
{
int u = query[i].first;
int v = query[i].second;
set<int> temp;

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。