#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
现在是什么现象?有测试用例没有
#include <iostream>
using namespace std;
struct node {
int data;
node* firstChild;
node* nextBrother;
};
node* CreateTree()
{
int k;
cin>>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 Find(node *root ,int n,int r = 1)
{
if(root == NULL)
return -1;
if(root->data == n)
return 1;
if(Find(root->firstChild,n,0) == 1)
return 1;
if(r==0)
return Find(root->nextBrother,n,0);
return -1;
}
int LeastCommonAncestors(node *root, int a, int b)
{
if(root == NULL)
return -1;
if(LeastCommonAncestors(root->firstChild,a,b) != -1)
return root->firstChild->data;
if(LeastCommonAncestors(root->nextBrother,a,b) != -1)
return root->nextBrother->data;
if(Find(root,a) == 1 && Find(root,b) == 1)
return root->data;
return -1;
}
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;
}
新手写代码不要着急写一大堆,写好一个函数就先运行了测试看看
目测你createtree就已经出问题了
既然强调了是树不是二叉树,你结构体里怎么会只有
firstChild 和nextBrother
你每一层应该是个链表的结构,要么是个数组的结构,而不是只有两个节点呀