7-4 是否同一棵二叉搜索树 (25分)

给定一个插入序列就可以唯一确定一棵二叉搜索树。然而，一棵给定的二叉搜索树却可以由多种不同的插入序列得到。例如分别按照序列{2, 1, 3}和{2, 3, 1}插入初始为空的二叉搜索树，都得到一样的结果。于是对于输入的各种插入序列，你需要判断它们是否能生成一样的二叉搜索树。

输入格式:

输入包含若干组测试数据。每组数据的第1行给出两个正整数N (≤)和L，分别是每个序列插入元素的个数和需要检查的序列个数。第2行给出N个以空格分隔的正整数，作为初始插入序列。最后L行，每行给出N个插入的元素，属于L个需要检查的序列。

简单起见，我们保证每个插入序列都是1到N的一个排列。当读到N为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

/*
    Name:
    Copyright:
    Author:  流照君
    Date: data
    Description:
*/
#include <iostream>
#include<string>
#include <algorithm>
#include <vector>
#define inf 100005
using namespace std;
typedef long long ll;
struct node{
	int n;
	node * lchlid;
	node * rchlid;
	node(int x){
		n=x;
		lchlid=NULL;
		rchlid=NULL;
	}
};
node* creat_tree(node* root,int x)
{
	   if(!root)
	   {
	   	root= new node(x);
	   }
	   else {
	    if(x>root->n)
	   {
	   	root->rchlid=creat_tree(root->rchlid,x);
	   }
	   else if(x<root->n)
	   {
	   	root->lchlid=creat_tree(root->lchlid,x);
	   } 
            }
	   return root;
} 
int cmp(node* l,node* r)
{
	if(l == NULL && r == NULL)
	 return 1;
	else if(l->n!=r->n)
	return 0;
	else if(l->n==r->n&&cmp(l->lchlid,r->lchlid)&&cmp(l->rchlid,r->rchlid))
	return 1;
	else
	return 0;
}
int main(int argc, char** argv)
{
#ifdef ONLINE_JUDGE//条件编译，如果有oj则忽略文件读取
#else
	//freopen("in.txt", "r", stdin);//输入输出文件重定向
	//freopen("out.txt", "w", stdout);
#endif  //#if, #ifdef, #ifndef这些条件命令的结束标志.
//代码位置
	 int N,L,x;
	 while(1)
	 {
	 cin>>N;
	 if(N==0)
	 return 0;
	 cin>>L;
	 node* root1=NULL,*root2=NULL;
	 for(int i=0;i<N;i++)
	 {
	 	cin>>x;
	 	root1=creat_tree(root1,x);
	 }
	 while(L--)
	 {
	 	root2=NULL;
		for(int i=0;i<N;i++)
	 	{
	 		cin>>x;
	 		root2=creat_tree(root2,x);
	 	}
	 	if(cmp(root1,root2))
	 	cout<<"Yes"<<endl;
	 	else
	 	cout<<"No"<<endl;
	 }
 }
    return 0;
}