时间限制：1 秒 内存限制：32 兆 特殊判题：否 提交：4894 解决：2183
题目描述：
判断两序列是否为同一二叉搜索树序列
输入：
开始一个数n，(1<=n<=20) 表示有n个需要判断，n= 0 的时候输入结束。
接下去一行是一个序列，序列长度小于10，包含(0~9)的数字，没有重复数字，根据这个序列可以构造出一颗二叉搜索树。
接下去的n行有n个序列，每个序列格式跟第一个序列一样，请判断这两个序列是否能组成同一颗二叉搜索树。
输出：
如果序列相同则输出YES，否则输出NO
样例输入：
2
567432
543267
576342
0
样例输出：
YES
NO
来源：
2010年浙江大学计算机及软件工程研究生机试真题
答疑：
解题遇到问题?分享解题心得?讨论本题请访问：http://t.jobdu.com/thread-7733-1-1.html
来源： http://ac.jobdu.com/problem.php?pid=1009
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
| /*
对输入数字序列构建二叉排序树，并对它们进行前序和中序遍历，
依次比较两次遍历结果是否相同，若相同则说明两棵二叉排序树
相同，否则不同
*/
#include<stdio.h>
#include<string.h>
typedef struct Node
{
struct Node *lchild;
struct Node *rchild;
int c;
}Node;
Node bTree[110];
int loc;
char str1[25],str2[25];
int size1,size2;
char *str;
int *size;
void preOrder(Node *T)
{
if(T!=NULL)
{
str[(*size)++]=T->c+'0';
preOrder(T->lchild);
preOrder(T->rchild);
}
}
void inOrder(Node *T)
{
if(T!=NULL)
{
inOrder(T->lchild);
str[(*size)++]=T->c+'0';
inOrder(T->rchild);
}
}
struct Node* insert(Node* T,int x)
{
if(!T)
{
T=&bTree[loc++];
T->c=x;
T->lchild=T->rchild=NULL;
return T;
}
else if(x<T->c) T->lchild=insert(T->lchild,x);
else if(x>T->c) T->rchild=insert(T->rchild,x);
return T;
};
int main()
{
#ifndef ONLINE_JUDGE
freopen("E:\jsj\cprojects\docs\in.txt","r",stdin);
//freopen("E:\jsj\cprojects\docs\mout.txt","w",stdout);
#endif
int n,i;
char tmp[12];
while(~scanf("%d",&n)&&n!=0)
{
Node *T=NULL;
scanf("%s",tmp);
for(loc=i=0;tmp[i]!=0;++i)
{
T=insert(T,tmp[i]-'0');
}
size1=0;
str=str1;
size=&size1;
preOrder(T);
inOrder(T);
str1[size1]=0;
while(n--!=0)
{
scanf("%s",tmp);
Node *T2=NULL;
for(i=0;tmp[i]!=0;++i)
{
T2=insert(T2,tmp[i]-'0');
}
size2=0;
str=str2;
size=&size2;
preOrder(T2);
inOrder(T2);
str2[size2]=0;
puts(strcmp(str1,str2)==0?"YES":"NO");
}
}
return 0;
}
|