题目地址
https://pta.patest.cn/pta/test/15/exam/4/question/712
5-4 是否同一棵二叉搜索树 (25分)
给定一个插入序列就可以唯一确定一棵二叉搜索树。然而，一棵给定的二叉搜索树却可以由多种不同的插入序列得到。例如分别按照序列{2, 1, 3}和{2, 3, 1}插入初始为空的二叉搜索树，都得到一样的结果。于是对于输入的各种插入序列，你需要判断它们是否能生成一样的二叉搜索树。
输入格式:
输入包含若干组测试数据。每组数据的第1行给出两个正整数NN (le 10≤10)和LL，分别是每个序列插入元素的个数和需要检查的序列个数。第2行给出NN个以空格分隔的正整数，作为初始插入序列。最后LL行，每行给出NN个插入的元素，属于LL个需要检查的序列。
简单起见，我们保证每个插入序列都是1到NN的一个排列。当读到NN为0时，标志输入结束，这组数据不要处理。
输出格式:
对每一组需要检查的序列，如果其生成的二叉搜索树跟对应的初始序列生成的一样，输出“Yes”，否则输出“No”。
输入样例:
4 2
3 1 4 2
3 4 1 2
3 2 4 1
2 1
2 1
1 2
0
输出样例:
Yes
No
No
鸣谢青岛大学周强老师补充测试数据！
/*时间 结果 得分 题目 编译器 用时（ms） 内存（MB） 用户
2017-06-28 19:34 答案正确 25 5-4 gcc 2 1
测试点结果
测试点 结果 得分/满分 用时（ms） 内存（MB）
测试点1 答案正确 12/12 2 1
测试点2 答案正确 8/8 2 1
测试点3 答案正确 3/3 2 1
测试点4 答案正确 2/2 2 1
*/
//建两棵树树然后比较树的方法，建树过程中卡壳，小测试数据没发现问题，修改if逻辑后ac
#include<stdio.h>
#include<stdlib.h>
#define __DEBUGPRINT //
typedef struct TreeNode *BSTTree;
typedef struct TreeNode{
int data;
BSTTree left;
BSTTree right;
int flag;
};
int Max(int a,int b)
{
return a>b ? a : b;
}
BSTTree BST_Insert(int x,BSTTree T)
{
if(T==NULL)
{
T=malloc(sizeof(struct TreeNode));
T->data=x;
T->left=NULL;
T->right=NULL;
T->flag=0;
return T;
}
if(x < T->data)
{
T->left=BST_Insert(x,T->left);
}
if(x > T->data)
{
T->right=BST_Insert(x,T->right);
}
return T;
}
void BST_CleanFlag(BSTTree T)
{
if (T!=NULL)
{
__DEBUGPRINT("+++Func Cleanflag T->data=%d
",T->data);
T->flag=0;
}
if(T->left != NULL)
BST_CleanFlag(T->left);
if(T->right != NULL)
BST_CleanFlag(T->right);
return;
}
void BST_Free(BSTTree T)
{
if(T!=NULL)
{
__DEBUGPRINT("+Func BST_Free T->data=%d
",T->data);
BST_Free(T->left);
BST_Free(T->right);
free(T);
}
}
void BST_Print(BSTTree T)
{
if(T!=NULL)
{
BST_Print(T->left);
printf(":%d ",T->data);
BST_Print(T->right);
}
}
int TreeCompare(BSTTree A,BSTTree B)
{
if(A==NULL && B== NULL)
{
__DEBUGPRINT("++compare node all null
A=%d,B=%d",A,B);
return 0;
}
else if((A==NULL && B!=NULL)||(A!=NULL && B==NULL))
{
__DEBUGPRINT("++one is null,one not
");
return 1;
}
else if(A->data !=B->data)
{
__DEBUGPRINT("++not same data
");
return 1;
}
else
{
__DEBUGPRINT("++begin to compare child
");
return Max(TreeCompare(A->left,B->left),TreeCompare(A->right,B->right));
}
}
int check(int x,BSTTree T)
{
if(T==NULL)
{
__DEBUGPRINT("++check ,x=%d,find a NULL node return 1
",x);
return 1;
}
if(T->flag==0)
{
if(x==T->data)
{
T->flag=1;
__DEBUGPRINT("++check ,x=%d,set a flag to node return 0
",x);
return 0;
}
else
{
__DEBUGPRINT("++check ,x=%d,T->data=%d,dismatch,return 1
",x,T->data);
return 1;
}
}
else if(x < T->data)
{
return check(x,T->left) ;
}
else if(x > T->data)
{
return check(x,T->right);
}
else return 1;
}
int func()
{
int i,j,N,L,temp,flag_all;
BSTTree A=NULL,B=NULL;
scanf("%d",&N);
if(N==0)
return 0;
scanf("%d",&L);
for(i=0;i<N;i++)
{
scanf("%d",&temp);
A=BST_Insert(temp,A);
}
//BST_Print(A);
//printf("
");
for(j=0;j<L;j++)
{
flag_all=0;
for(i=0;i<N;i++)
{
scanf("%d",&temp);
B=BST_Insert(temp,B);
}
flag_all=TreeCompare(A,B);
//BST_Print(B);
//printf("
");
BST_Free(B);
B=NULL;
if(flag_all>0)
printf("No
");
else
printf("Yes
");
}
BST_Free(A);
return 1;
}
int main()
{
while(func());
}