HDU3791二叉搜索树（浙大计算机研究生复试上机考试-2010年 ）

Problem Description

判断两序列是否为同一二叉搜索树序列

Input

开始一个数n，(1<=n<=20) 表示有n个需要判断，n= 0 的时候输入结束。
接下去一行是一个序列，序列长度小于10，包含(0~9)的数字，没有重复数字，根据这个序列可以构造出一颗二叉搜索树。
接下去的n行有n个序列，每个序列格式跟第一个序列一样，请判断这两个序列是否能组成同一颗二叉搜索树。

Output

如果序列相同则输出YES，否则输出NO

Sample Input

2

567432

543267

576342

0

Sample Output

YES

NO

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3791

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
const int N=15;
int a[N],b[N];
int cnt=0;
typedef struct tree{
int x;
tree *l,*r;
}tree;tree * create(int x)
{tree *root=(tree*)malloc(sizeof(tree));//动态申请内存root->x=x;root->l=NULL;root->r=NULL;return root;//返回指针
}
tree *Insert(tree *root,int x)
{if(root==NULL)//根节点为空，创造二叉树{root=create(x);}else{if(x>root->x)//右子树{root->r=Insert(root->r,x);}else{root->l=Insert(root->l,x);//左子树}}return root;
}
void Traversal(tree * root)
{if(root!=NULL)//节点不为空遍历，左子树和右子树{b[cnt++]=root->x;Traversal(root->l);Traversal(root->r);}
}
void destroy(tree *root)//销毁二叉树
{if(root){destroy(root->l);destroy(root->r);delete root;}
}
int main()
{int n;while(cin>>n,n){cnt=0;tree *root=NULL;char str[N];cin>>str;int len=strlen(str);for(int i=0;i<len;i++){root=Insert(root,str[i]-'0');}Traversal(root);for(int i=0;i<len;i++){a[i]=b[i];}while(n--){cnt=0;cin>>str;destroy(root);root=NULL;for(int i=0;i<len;i++){root=Insert(root,str[i]-'0');}Traversal(root);int i;for( i=0;i<len;i++){if(a[i]!=b[i]){cout<<"NO"<<endl;break;}}if(i>=len)cout<<"YES"<<endl;}}return 0;
}

-----------------------------------------------------------------------------------------------------------------------------------------------------------------2018,9.19，思路差不多，重新写了一遍

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
const int N=30;
int a[N],b[N];
int cnt=0;
typedef struct node{
int x;
struct node * r=NULL;
struct node* l=NULL;
}Node;
Node * create(int x)
{Node *root=(Node*)malloc(sizeof(Node));root->x=x;root->l=NULL;root->r=NULL;return root;
}
Node * Insert(Node *root,int x)
{if(!root){root=create(x);}else{if(x>root->x)root->r=Insert(root->r,x);elseroot->l=Insert(root->l,x);}return root;
}void Travel(Node *root){if(root!=NULL){b[cnt++]=root->x;Travel(root->l);Travel(root->r);}}
int main()
{int n;string str;while(cin>>n,n){cnt=0;Node *root=NULL;cin>>str;int len=str.length();for(int i=0;i<len;i++){root=Insert(root,str[i]-'0');}Travel(root);for(int i=0;i<len;i++){a[i]=b[i];}while(n--){cnt=0;cin>>str;root=NULL;for(int i=0;i<len;i++){root=Insert(root,str[i]-'0');}Travel(root);int flag=1;for( int i=0;i<len;i++){if(a[i]!=b[i]){flag=0;cout<<"NO"<<endl;break;}}if(flag)cout<<"YES"<<endl;}}
}