多叉树最近公共祖先问题（LCA）
任务：设计一个算法，对于给定的树中两结点，返回它们的最近公共祖先
输入：第1行有一个正整数n，表示给定的树有n个结点。结点编号为1,2,3,...,n，编号为1的顶点是树根。接下来n行中，第i+1行描述了第i个结点的儿子情况。每行的第一个正整数k表示该结点有k个儿子，其后k个数中，每一个数表示其儿子结点的编号。当k=0时表示该结点为叶节点。
输入的第n+2行是一个正整数m，表示要计算最近公共祖先的m个结点对。接下来的m行，每行两个正整数，前两个是结点编号，第3个是它们的最近公共祖先结点编号。
输入样例：
12
3 2 3 4
2 5 6
0
0
2 7 8
2 9 10
0
【多叉树最近公共祖先问题（LCA）】0
0
2 11 12
0
0
5
3 11
7 12
4 8
9 12
8 10
输出样例：
3 11 1
7 12 2
4 8 1
9 12 6
8 10 2
文章图片
不会什么高深的算法，直接暴力搜索了。其实还可以稍微优化一下，即存储路径时只需要存储一条，然后让另一个结点一直回溯，比较判断就好了。不过想到这个的时候已经写完了，也没心思去改了、、、
#include
#include
using namespace std;
typedef struct{
int parent;
int *son;
}TreeNode;
void findPath(TreeNode* node, int x, vector& path)
{
int i;
// 找出该结点到根结点的路径
// 因根结点父节点已标记为0，故以此为循环结束条件
while( node[x].parent != 0 ){
i = node[x].parent;
path.push_back(i);
x = i;
}
}int find_ClosetParent(vector& path_a, vector& path_b)
{
// O( path_a.size() * path_b.size() )
for(int i = 0;
i < path_a.size();
++i)
for(int k = 0;
k < path_b.size();
++k)
if( path_a[i] == path_b[k] )
return path_a[i];
return -1;
// 若结点对有一个是根结点，则找不到
} int main()
{
int n, m, k, pos;
while( cin >> n )
{
TreeNode node[n+1];
// 构建树
node[1].parent = 0;
//根结点的父亲结点下标标记为0
for(int i = 1;
i <= n;
++i){
//cout << "node " << i << endl;
cin >> k;
node[i].son = (k!=0) ? (new int[k]):nullptr;
//m为0表示没有儿子
for(int j = 0;
j < k;
++j){
cin >> pos;
node[pos].parent = i;
//将该儿子结点的父节点标记为当前结点
node[i].son[j] = pos;
//存储该结点的儿子结点下标
}
}
// 寻找公共祖先结点
int a, b, res;
cin >> m;
while( m-- ){
//cout << "opt " << endl;
vector path_a, path_b;
cin >> a >> b;
// 加速优化
if( a==b || node[a].parent==node[b].parent ){
res = node[a].parent;
}else{
findPath(node, a, path_a);
findPath(node, b, path_b);
res = find_ClosetParent(path_a, path_b);
}
cout << a << " " << b << " " << res << endl;
}
// 释放node数组开辟的son数组空间
for(int i = 1;
i <= n;
++i)
delete[] node[i].son;
cout << "-----END-----" << endl;
}
return 0;
} 推荐阅读
- JS中的各种宽高度定义及其应用
- 人生感悟记＃环境仪器宋庆国成长记＃072
- “精神病患者”的角度问题
- 【生信技能树】R语言练习题|【生信技能树】R语言练习题 - 中级
- 放下心中的偶像包袱吧
- java中如何实现重建二叉树
- 疲困，却仍得继续
- 种树郭橐驼传（文言句式+古今异义+词类活用+通假字）
- RxJava|RxJava 在Android项目中的使用（一）
- 白杨树