返回信息流就是一颗倒的二叉树，也就是说都是子节点指向父节点，树上的任意两个节点A和B，如何确定他们的公共父亲节点？？？有人说很简单，他就是不告诉我怎么做。
这是一条镜像帖。来源：北邮人论坛 / cpp / #38681同步于 2010/4/28
该镜像源已超过 30 天没有更新，可能在源站已被删除。
CPP机器人发帖
【求助】倒向二叉树的问题
Q19851104
2010/4/28镜像同步4 回复
订阅后，新回复会通过你的通知中心匿名送达。
4 条回复
1,最近公共祖先(LCA):
对于有根树T的两个结点u、v，最近公共祖先LCA(T,u,v)表示一个结点x，满足x是u、v的祖先且x的深度尽可能大。
2,LCA问题向RMQ问题的转化方法:(RMQ返回最值的下标)
对树进行深度优先遍历，每当“进入”或回溯到某个结点时，将这个结点的深度存入数组dfsNum最后一位。同时记录结点i在数组中第一次出现的位置(事实上就是进入结点i时记录的位置)，记做first[i]。如果结点dfsNum[i]的深度记做depth[i]，易见，这时求 LCA(u,v)，就等价于求 E[RMQ(depth,first[u],first[v])]，(first[u]<first[v])。
例如:(图片)
(深度遍历)difNum[i]为：1,2,1,3,4,3,5,3,1
first[i]为：0,1,3,4,6
(个点对应的深度)depth[i]为：0,1,0,1,2,1,2,1,0
于是有：
LCA(4,1) = difNum[RMQ(D,first[1],R[4])] = difNum[RMQ(D,1,6)] = difNum[2] = 1
转化后得到的数列长度为树的结点数*2-1（每经过一条边，都会记录端点，有N-1条边，所以会回溯N-1次。且每个顶点都会被添加一次，所以长度为2N-1）
3，lz想要代码,手头正好有个.
bless
#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=20010;
struct node //可以添加额外的信息
{
int v;//孩子结点
};
//注意vector在树问题中的使用
vector<node> tree[maxn];
int dfsnum[maxn]; //记录遍历的节点
int depth[maxn]; //记录节点对应的深度
int first[maxn]; //记录结点第一次访问到时的下标
int top; //记录总的步伐数
void dfs(int m,int f,int dep) //当前节点编号,父节点编号,深度
{
dfsnum[top]=m;
depth[top]=dep;
first[m]=top;
top++;
for(unsigned i=0;i<tree[m].size();i++)
{
if(tree[m][i].v==f)
continue;
dfs(tree[m][i].v,m,dep+1);
dfsnum[top]=m; //注:每条边回溯一次,所以top的值=n+n-1
depth[top]=dep;
top++;
}
}
int dp[maxn][18];
void makeRmqIndex(int n,int b[]) //返回最小值对应的下标
{
int i,j;
for(i=0;i<n;i++)
dp[i][0]=i;
for(j=1;(1<<j)<=n;j++)
for(i=0;i+(1<<j)-1<n;i++)
dp[i][j]=b[dp[i][j-1]] < b[dp[i+(1<<(j-1))][j-1]]? dp[i][j-1]:dp[i+(1<<(j-1))][j-1];
}
int rmqIndex(int s,int v,int b[])
{
int k=(int)(log((v-s+1)*1.0)/log(2.0));
return b[dp[s][k]]<b[dp[v-(1<<k)+1][k]]? dp[s][k]:dp[v-(1<<k)+1][k];
}
int lca(int x,int y)
{
return dfsnum[rmqIndex(first[x],first[y],depth)];
}
int main()
{
int n=5;//顶点数
top=0;
//分别存放每条边的端点
int x[]={1,1,3,3};
int y[]={2,3,4,5};
node temp;
for(int i=0;i<n-1;i++) //n-1条边
{
temp.v=y[i];
tree[x[i]].push_back(temp);
temp.v=x[i];
tree[y[i]].push_back(temp);
}
dfs(1,-1,0); //根节点为1
cout<<"总数:"<<top<<endl;
makeRmqIndex(top,depth);
cout<<"dfsnum:";
for(int i=0;i<top;i++)
{
cout<<dfsnum[i]<<" ";
}
cout<<endl;
cout<<"depth:";
for(int i=0;i<top;i++)
{
cout<<depth[i]<<" ";
}
cout<<endl;
cout<<"first:";
for(int i=1;i<=n;i++)
{
cout<<first[i]<<" ";
}
cout<<endl;
cout<<"lca(4,5):"<<lca(4,5)<<endl;
cout<<"lca(2,4):"<<lca(2,4)<<endl;
cout<<"lca(1,4):"<<lca(1,4)<<endl;
return 0;
}
【 在 vist 的大作中提到: 】
: complicate
: --
要好好自己思考，这个应该是老师布置的作业。
不行了可以去问问老师，会给你讲得很清楚，比在论坛上问学到的更深刻
【 在 Q19851104 的大作中提到: 】
: 就是一颗倒的二叉树，也就是说都是子节点指向父节点，树上的任意两个节点A和B，如何确定他们的公共父亲节点？？？有人说很简单，他就是不告诉我怎么做。