函数题：树最近公共祖先
已知树结点为互不相等且不等于0的整数。请编写程序找出非空树中两个结点的最近公共祖先。例如对于图1(a)所示的树t，结点1和2的最近公共祖先是5；结点2和4的最近公共祖先是8。
注：在本题中你只需按照下面函数接口定义实现核心函数即可，无需编写main函数及处理输入输出。
### 函数接口定义：
c++
在本题中你无需编写整个程序，只需实现如下函数
int LeastCommonAncestors(node *root, int a, int b);
该函数功能为在以root为根的树中，查找结点a和b的最近公共祖先，并返回其数据域之值。
### 框架程序代码：
c++
#include<stdio.h>
using namespace std;
struct node {
int data;
node* firstChild;
node* nextBrother;
};
node* CreateTree()
{
int k;
scanf("%d", &k);
if (k == 0) return NULL;
node *t = new node;
t->data = k;
t->firstChild = CreateTree();
t->nextBrother = CreateTree();
return t;
}
void Del(node* root)
{
if (root == NULL) return;
node* p = root->firstChild;
node* next;
while (p != NULL){
next = p->nextBrother;
Del(p);
p = next;
}
delete root;
}
/* 你的代码将出现在这里 */
int main()
{
int a, b, T;
scanf("%d", &T);
while(T--){
node *root = CreateTree();
scanf("%d %d", &a, &b);
printf("%d\n", LeastCommonAncestors(root, a, b));
Del(root);
}
return 0;
}
### 输入格式:
每个测试点包含多组数据，第1行为一个正整数T，表示数组组数。每组数据为2行，第1行为一组用空格间隔的整数，个数不超过100个，表示带空指针信息的二叉树先根序列。其中空指针信息用0表示。第2行为空格间隔的两个互不相等的整数A和B，表示给定的两个结点值，保证A和B肯定在输入的树中。
注1：我们已知二叉树与其自然对应的树相比，二叉树中结点的左孩子对应树中结点的左孩子，二叉树中结点的右孩子对应树中结点的右兄弟。进而我们可以利用“带空指针信息的先根序列构建二叉树”的方法来构建其对应的树的左孩子-右兄弟存储结构。如8 5 1 0 6 0 2 0 0 3 4 0 0 7 0 0 0对应图1(a)所示的树，1 2 0 3 0 4 0 0 0对应如图1(b)所示的树。
**注2：本题中读入数据的操作无需你来完成，而由框架程序完成。**
### 输出格式:
对每组数据输出一行，为一个整数，表示A和B的最近公共祖先结点的值。
**注：本题的输出由框架程序完成，无需你来输出。**
### 输入样例：
in
2
8 5 1 0 6 0 2 0 0 3 4 0 0 7 0 0 0
1 2
8 5 1 0 6 0 2 0 0 3 4 0 0 7 0 0 0
2 4
### 输出样例：
out
5
8
答案：若无答案欢迎评论
注：在本题中你只需按照下面函数接口定义实现核心函数即可，无需编写main函数及处理输入输出。
### 函数接口定义：
c++
在本题中你无需编写整个程序，只需实现如下函数
int LeastCommonAncestors(node *root, int a, int b);
该函数功能为在以root为根的树中，查找结点a和b的最近公共祖先，并返回其数据域之值。
### 框架程序代码：
c++
#include<stdio.h>
using namespace std;
struct node {
int data;
node* firstChild;
node* nextBrother;
};
node* CreateTree()
{
int k;
scanf("%d", &k);
if (k == 0) return NULL;
node *t = new node;
t->data = k;
t->firstChild = CreateTree();
t->nextBrother = CreateTree();
return t;
}
void Del(node* root)
{
if (root == NULL) return;
node* p = root->firstChild;
node* next;
while (p != NULL){
next = p->nextBrother;
Del(p);
p = next;
}
delete root;
}
/* 你的代码将出现在这里 */
int main()
{
int a, b, T;
scanf("%d", &T);
while(T--){
node *root = CreateTree();
scanf("%d %d", &a, &b);
printf("%d\n", LeastCommonAncestors(root, a, b));
Del(root);
}
return 0;
}
### 输入格式:
每个测试点包含多组数据，第1行为一个正整数T，表示数组组数。每组数据为2行，第1行为一组用空格间隔的整数，个数不超过100个，表示带空指针信息的二叉树先根序列。其中空指针信息用0表示。第2行为空格间隔的两个互不相等的整数A和B，表示给定的两个结点值，保证A和B肯定在输入的树中。
注1：我们已知二叉树与其自然对应的树相比，二叉树中结点的左孩子对应树中结点的左孩子，二叉树中结点的右孩子对应树中结点的右兄弟。进而我们可以利用“带空指针信息的先根序列构建二叉树”的方法来构建其对应的树的左孩子-右兄弟存储结构。如8 5 1 0 6 0 2 0 0 3 4 0 0 7 0 0 0对应图1(a)所示的树，1 2 0 3 0 4 0 0 0对应如图1(b)所示的树。
**注2：本题中读入数据的操作无需你来完成，而由框架程序完成。**
### 输出格式:
对每组数据输出一行，为一个整数，表示A和B的最近公共祖先结点的值。
**注：本题的输出由框架程序完成，无需你来输出。**
### 输入样例：
in
2
8 5 1 0 6 0 2 0 0 3 4 0 0 7 0 0 0
1 2
8 5 1 0 6 0 2 0 0 3 4 0 0 7 0 0 0
2 4
### 输出样例：
out
5
8
答案：若无答案欢迎评论
