http://ac.jobdu.com/problem.php?pid=1009
- 题目描述：
-
判断两序列是否为同一二叉搜索树序列
- 输入：
-
开始一个数n，(1<=n<=20) 表示有n个需要判断，n= 0 的时候输入结束。
接下去一行是一个序列，序列长度小于10，包含(0~9)的数字，没有重复数字，根据这个序列可以构造出一颗二叉搜索树。
接下去的n行有n个序列，每个序列格式跟第一个序列一样，请判断这两个序列是否能组成同一颗二叉搜索树。
- 输出：
-
如果序列相同则输出YES，否则输出NO
- 样例输入：
-
2 567432 543267 576342 0
- 样例输出：
-
YES NO
#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
using namespace std;
int loc;
struct Node{
Node *lchild;
Node *rchild;
char c;
}Tree[50];
Node *creat(){
Tree[loc].lchild = Tree[loc].rchild = NULL;
return &Tree[loc++];
}
Node *insert(Node *T, char x){
if (T == NULL){
T = creat();
T->c = x;
}
else{
if (x < T->c)
T->lchild = insert(T->lchild, x);
else if (x > T->c)
T->rchild = insert(T->rchild, x);
}
return T;
}
void preOrder(Node *T, string &s){
s += T->c;
if (T->lchild != NULL)
preOrder(T->lchild, s);
if (T->rchild != NULL)
preOrder(T->rchild, s);
}
void inOrder(Node *T, string &s){
if (T->lchild != NULL)
inOrder(T->lchild, s);
s += T->c;
if (T->rchild != NULL)
inOrder(T->rchild, s);
}
int main(){
int n;
string str1, str2, s1, s2;
while (scanf("%d", &n) != EOF && n != 0){
cin >> str1;
loc = 0;
Node *k = NULL;
for (int j = 0; j < str1.size(); j++)
k = insert(k, str1[j]);
s1 = "";
preOrder(k, s1);
inOrder(k, s1);
for (int i = 0; i < n; i++){
cin >> str2;
loc = 0;
Node *r = NULL;
for (int j = 0; j < str2.size(); j++)
r = insert(r, str2[j]);
s2 = "";
preOrder(r, s2);
inOrder(r, s2);
if (s1 == s2)
puts("YES");
else puts("NO");
}
}
return 0;
}