题目描述

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

输入描述:

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

输出描述:

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

链接：https://www.nowcoder.com/questionTerminal/3d6dd9a58d5246f29f71683346bb8f1b
来源：牛客网

#include<stdio.h>
#include<string.h>
typedef struct TNode{
    char data;
    struct TNode *left,*right;
}*BiTree,TNode;
TNode T[200];
int loc;
int size;
BiTree creat(){
    T[loc].left=T[loc].right=NULL;
    return &T[loc++];
}
BiTree Insert(BiTree T,char x){
    if(!T){
        T=creat();
        T->data=x;
        return T;
    }
    if(x<T->data)
        T->left=Insert(T->left,x);
    else if(x>T->data)
        T->right=Insert(T->right,x);
    return T;
}
void PreOrder(BiTree T,char pre[]){
    if(!T) return;
    pre[size++]=T->data;
    pre[size]=0;
    PreOrder(T->left,pre);
    PreOrder(T->right,pre);
    return;
}
int main(){
    BiTree T1,T2;
    int n;
    while(scanf("%d",&n)!=EOF&&n!=0){
        getchar();
        T1=NULL;
        loc=0;
        char str1[12],str2[12];
        gets(str1);
        for(int i=0;str1[i]!=0;i++)
            T1=Insert(T1,str1[i]);
        for(int i=0;i<n;i++){
            T2=NULL;
            gets(str2);
            for(int i=0;str2[i]!=0;i++)
                T2=Insert(T2,str2[i]);
            char a[24],b[24];
            PreOrder(T1,a);
            size=0;
            PreOrder(T2,b);
            size=0;
            puts(strcmp(a,b)==0?"YES":"NO");
        }
    }
    return 0;
}