#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 LeastCommonAncestors(node *root, int a, int b){
if(root==NULL)
return -1;
if(root->data==a||root->data==b)
return root->data;
int fC=LeastCommonAncestors(root->firstChild, a, b);
int nB=LeastCommonAncestors(root->nextBrother, a, b);
if(fC==-1){
return nB;
}
if(nB==-1){
return fC;
}
return root->data;
}
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;
}
不知道要怎么修改
输入
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
输出
5
8