7-11 是否同一棵二叉搜索树 （25 分)
给定一个插入序列就可以唯一确定一棵二叉搜索树。然而，一棵给定的二叉搜索树却可以由多种不同的插入序列得到。例如分别按照序列{2, 1, 3}和{2, 3, 1}插入初始为空的二叉搜索树，都得到一样的结果。于是对于输入的各种插入序列，你需要判断它们是否能生成一样的二叉搜索树。
输入格式:
输入包含若干组测试数据。每组数据的第1行给出两个正整数 ()和，分别是每个序列插入元素的个数和需要检查的序列个数。第2行给出个以空格分隔的正整数，作为初始插入序列。最后行，每行给出个插入的元素，属于个需要检查的序列。
简单起见，我们保证每个插入序列都是1到的一个排列。当读到为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
鸣谢青岛大学周强老师补充测试数据！
#include<bits/stdc++.h>
using namespace std;
int n,l,num;
void Insert(int *a,int root,int num)
{
if(a[root]==-1)
{
a[root] = num;return;
}
else if(num<a[root])Insert(a,root<<1,num);
else Insert(a,root<<1|1,num);
}
int cmp(int *a,int *b)
{
for(int i=1; i<=100; i++)
{
if(a[i]!=b[i])return 0;
}
return 1;
}
int a[2090],b[2090];
int main()
{
while(cin>>n&&n)
{
memset(a,-1,sizeof(a));
cin>>l;
for(int i=1; i<=n; i++)
{
cin>>num;
Insert(a,1,num);
}
while(l--)
{
memset(b,-1,sizeof(b));
for(int i=1; i<=n; i++)
{
cin>>num;
Insert(b,1,num);
}
if(cmp(a,b))printf("Yes\n");
else printf("No\n");
}
}
return 0;
}CODE2
#include<bits/stdc++.h>
using namespace std;
int a[1231234],b[1231234];
void Insert(int *a,int root,int num)
{
if(a[root]==0)
{
a[root] = num;
return ;
}
else if(num<a[root])Insert(a,root<<1,num);
else Insert(a,root<<1|1,num);
}
int judge(int root1,int root2)
{
if(!a[root1]&&!b[root2])return 1;
if(a[root1]!=b[root2])return 0;
else return judge(root1<<1,root2<<1)&&judge(root1<<1|1,root2<<1|1);
}
int main()
{
int n,m,g;
while(cin>>n)
{
if(n==0)break;
cin>>m;
memset(a,0,sizeof a);
for(int i=1; i<=n; i++)
{
scanf("%d",&g);
Insert(a,1,g);
}
while(m--)
{
memset(b,0,sizeof b);
for(int i=1; i<=n; i++)
{
scanf("%d",&g);
Insert(b,1,g);
}
int f = judge(1,1);
if(f)printf("Yes\n");
else printf("No\n");
}
}
}