问题 B: 进击的二叉查找树
时间限制: 1 Sec
内存限制: 64 MB
提交: 1017
解决: 379
题目描述
给定1~N的两个排列，使用这两个排列分别构建两棵二叉查找树（也就是通过往一棵空树中依次插入序列元素的构建方式）。如果这两棵二叉查找树完全相同，那么输出YES；否则输出NO。之后，输出第一个排列对应的二叉查找树的后序序列、层序序列。
输入
每个输入文件中一组数据。
第一行1个正整数N（1<=N<=30），表示二叉查找树中的结点个数。
接下来两行，代表1~N的两个排列。
输出
如果两个排列代表的二叉查找树完全相同，那么输出一行YES，否则输出一行NO。
接下来两行分别输出第一个排列对应的二叉查找树的后序序列、层序序列，整数之间用空格隔开。
每行末尾不允许有多余的空格。
样例输入
5
4 2 1 3 5
4 5 2 3 1
4 2 1 3 5
4 5 2 3 1
样例输出
YES
1 3 2 5 4
4 2 5 1 3
代码：
1 3 2 5 4
4 2 5 1 3
代码：
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
typedef struct BiTNode
{
int data;
struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;
int pos=0;
int BSTInsert(BiTree *t, int element)
{
if(NULL==*t)
{
(*t)=(BiTree)malloc(sizeof(BiTNode));
(*t)->data=element;
(*t)->lchild=(*t)->rchild=NULL;
return 1;
}
if(element==(*t)->data)
return 0;
if(element<(*t)->data)
return BSTInsert(&(*t)->lchild,element);
return BSTInsert(&(*t)->rchild,element);
}
void CreateBST(BiTree *t, int *a, int n)
{
(*t) = NULL;
for( int i=0; i<n; i++ )
BSTInsert(t,a[i]);
}
void PrintBST(BiTree t, int a[])
{
if(t)
{
PrintBST(t->lchild,a);
PrintBST(t->rchild,a);
a[pos]=t->data;
pos++;
}
}
bool isEqual(BiTree t1, BiTree t2)
{
if(t1==NULL&&t2==NULL)
return true;
else if(t1==NULL||t2==NULL)
return false;
else
{
if(t1->data!=t2->data)
return false;
else
{
bool isEqualLeft,isEqualRight;
isEqualLeft=isEqual(t1->lchild,t2->lchild);
isEqualRight=isEqual(t1->rchild,t2->rchild);
if(isEqualLeft&&isEqualRight)
return true;
else
{
isEqualLeft=isEqual(t1->lchild,t2->rchild);
isEqualRight=isEqual(t1->rchild,t2->lchild);
if(isEqualLeft&&isEqualRight)
return true;
else
return false;
}
}
}
}
void printLevel(BiTree t, int a[], int index)
{
queue<BiTree> q;
if(t!=NULL)
q.push(t);
BiTree b;
while(!q.empty())
{
b=q.front();
a[index]=b->data;
index++;
q.pop();
if(b->lchild)
q.push(b->lchild);
if(b->rchild)
q.push(b->rchild);
}
}
int main()
{
int n;
int *a,*b;
BiTree t1,t2;
scanf("%d", &n);
a=(int*)malloc(sizeof(int)*n);
b=(int*)malloc(sizeof(int)*n);
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
for(int i=0;i<n;i++)
scanf("%d",&b[i]);
CreateBST(&t1,a,n);
CreateBST(&t2,b,n);
if(isEqual(t1,t2))
printf("YES\n");
else
printf("NO\n"); PrintBST(t1,a);
printf("%d",a[0]);
for(int i=1;i<n;i++)
{
printf(" %d",a[i]);
}
printf("\n");
printLevel(t1,a,0);
printf("%d",a[0]);
for(int i=1;i<n;i++)
{
printf(" %d",a[i]);
}
printf("\n");
return 0;
}