算法-一个二叉树公共节点的算法

Question

现有一个二叉树，节点数未知，给2个节点，请找出这2个节点的最底层公共父节点。给出思路或程序实现

Answer 1

典型的有根树最小公共祖先
最近公共祖先LCA:Tarjan算法

1,并查集+dfs
对整个树进行深度优先遍历，并在遍历的过程中不断地把一些目前可能查询到的并且结果相同的节点用并查集合并.

2,分类，使每个结点都落到某个类中，到时候只要执行集合查询，就可以知道结点的LCA了。
对于一个结点u.类别有:
以u为根的子树、除类一以外的以f(u)为根的子树、除前两类以外的以f(f(u))为根的子树、除前三类以外的以f(f(f(u)))为根的子树……

类一的LCA为u,类二为f(u),类三为f(f(u)),类四为f(f(f(u)))。这样的分类看起来好像并不困难。
但关键是查询是二维的，并没有一个确定的u。接下来就是这个算法的巧妙之处了。
利用递归的LCA过程。
当lca(u)执行完毕后，以u为根的子树已经全部并为了一个集合。而一个lca的内部实际上做了的事就是对其子结点，依此调用lca.
当v1(第一个子结点)被lca，正在处理v2的时候，以v1为根的子树＋u同在一个集合里，f(u)+编号比u小的u的兄弟的子树　同在一个集合里，f(f(u))　+　编号比f(u)小的　f(u)的兄弟　的子树　同在一个集合里……
而这些集合，对于v2的LCA都是不同的。因此只要查询x在哪一个集合里，就能知道LCA(v2,x)

还有一种可能，x不在任何集合里。当他是v2的儿子，v3,v4等子树或编号比ｕ大的ｕ的兄弟的子树（等等）时，就会发生这种情况。即还没有被处理。还没有处理过的怎么办？把一个查询(x1,x2)往查询列表里添加两次，一次添加到x1的列表里，一次添加到x2的列表里，如果在做x1的时候发现 x2已经被处理了，那就接受这个询问。（两次中必定只有一次询问被接受）.

#include<iostream>
#include<vector>
using namespace std;

const int MAX=10001;
int f[MAX];
int r[MAX];
int indegree[MAX];//保存每个节点的入度
int visit[MAX];
vector<int> tree[MAX],Qes[MAX];
int ancestor[MAX];

void init(int n)
{
for(int i=1;i<=n;i++)
{

r[i]=1;
f[i]=i;
indegree[i]=0;
visit[i]=0;
ancestor[i]=0;
tree[i].clear();
Qes[i].clear();
}

}

int find(int n)
{
if(f[n]==n)
return n;
else
f[n]=find(f[n]);
return f[n];
}//查找函数，并压缩路径

int Union(int x,int y)
{
int a=find(x);
int b=find(y);
if(a==b)
return 0;
//相等的话,x向y合并
else if(r[a]<=r[b])
{
f[a]=b;
r[b]+=r[a];
}
else
{
f[b]=a;
r[a]+=r[b];
}
return 1;

}//合并函数，如果属于同一分支则返回0，成功合并返回1

void LCA(int u)
{
ancestor[u]=u;
int size = tree[u].size();
for(int i=0;i<size;i++)
{
LCA(tree[u][i]);
Union(u,tree[u][i]);
ancestor[find(u)]=u;
}
visit[u]=1;
size = Qes[u].size();
for(int i=0;i<size;i++)
{
//如果已经访问了问题节点,就可以返回结果了.
if(visit[Qes[u][i]]==1)
{
cout<<ancestor[find(Qes[u][i])]<<endl;
return;
}
}
}

int main()
{
int cnt;
int n;
cin>>cnt;
while(cnt--)
{
cin>>n;;
init(n);
int s,t;
for(int i=1;i<n;i++)
{
cin>>s>>t;
tree[s].push_back(t);
indegree[t]++;
}
//这里可以输入多组询问
cin>>s>>t;
//相当于询问两次
Qes[s].push_back(t);
Qes[t].push_back(s);
for(int i=1;i<=n;i++)
{
//寻找根节点
if(indegree[i]==0)
{
LCA(i);
break;
}
}
}
return 0;
}

资料参考:http://kmplayer.iteye.com/blog/604518

Answer 2

这个就是2叉树 两个结点找爹，其实我个人建议，如果是用链表的数据结构把，那么在每个结点中1。有他父亲结点。2.有一个num 代表他们在树中的顺序。
具体思路呢 就是从结点num中大的开始，num1=他父亲结点的num，一直这样 知道num1>=num2
这时num2也开始同样的事情。最后找到num1==num2 那么这个就是要找到的最近的结点。
具体代码：这里我用存储的是数组，链表也是同一回事的。
int num1=4;
int num2=6;
while(num2!=num1){
if(num2>num1){
num2=t[num2-1].tt.num;
}
else{
num1=t[num1-1].tt.num;
}
}
System.out.println("the same father is "+num1+" "+num2);

Answer 3

算法思路：首先给出p的父节点p->parent，然后将q的所有父节点依次和p->parent作比较，如果发现两个节点相等，则该节点就是最近公共祖先，直接将其返回。如果没找到相等节点，则将q的所有父节点依次和p->parent->parent作比较......直到p->parent==root。实现代码：

class Node
{
Node * left;
Node * right;
Node * parent;
};

Node * NearestCommonAncestor(Node * root,Node * p,Node * q)
{
Node * temp;
while(p!=NULL)
{
p=p->parent;
temp=q;
while(temp!=NULL)
{
if(p==temp->parent)
return p;
temp=temp->parent;
}
}
}

/*查找p，q的最近公共祖先并将其返回。*/
Node * NearestCommonAncestor(Node * p,Node * q);

来源网络