题目1009：二叉搜索树

题目描述：

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

输入：

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

输出：

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

样例输入：

2
567432
543267
576342
0

样例输出：

YES
NO

Code:

#include <iostream>
#include <string.h>
 
using namespace std;
 
struct Node{
    int data;
    Node *lchild;
    Node *rchild;
}Tree[20];
 
int loc;
char str1[20],str2[20];
 
Node *create(){
    Tree[loc].lchild=Tree[loc].rchild=NULL;
    return &Tree[loc++];
}
 
Node *insertNode(Node *T,int x){
    if(T==NULL){
        T=create();
        T->data=x;
        return T;
    }
    if(x<T->data){
        T->lchild=insertNode(T->lchild,x);
    }
    if(T->data<x){
        T->rchild=insertNode(T->rchild,x);
    }
    return T;
}
 
int cnt;
char str[20];
 
char *inOrder(Node *T){
    if(T!=NULL){
        if(T->lchild!=NULL){
            inOrder(T->lchild);
        }
        if(T->rchild!=NULL){
            inOrder(T->rchild);
        }
        str[cnt++]=T->data;
    }
    return str;
}
 
bool judge(char a[],int len_a,char b[],int len_b){
    for(int i=0,j=0;i<len_a&&j<len_b;++i,++j){
        if(a[i]!=b[j]){
            return false;
        }
    }
    return true;
}
 
char *str1_buf,*str2_buf;    
 
int main()
{
    int n;
    while(cin>>n){
        if(n==0)
            break;
        cin>>str1;
        int len_str1=strlen(str1);
        Node *T_str1=NULL;
        loc=0;
        cnt=0;
        for(int k=0;k<len_str1;++k){
            T_str1=insertNode(T_str1,str1[k]);
        }
        str1_buf=inOrder(T_str1);
        char temp_buf[20];
        for(int i=0;i<len_str1;++i){
            temp_buf[i]=str1_buf[i];
        }
        for(int i=0;i<n;++i){
            cin>>str2;
            int len_str2=strlen(str2);
            Node *T_str2=NULL;
            loc=0;
            cnt=0;
            for(int k=0;k<len_str2;++k){
                T_str2=insertNode(T_str2,str2[k]);
            }
            str2_buf=inOrder(T_str2);
            bool flag=judge(temp_buf,len_str1,str2_buf,len_str2);
            if(flag==true){
                cout<<"YES"<<endl;
            }
            else{
                cout<<"NO"<<endl;
            }
        }
    }
    return 0;
}
 
/**************************************************************
    Problem: 1009
    User: lcyvino
    Language: C++
    Result: Accepted
    Time:0 ms
    Memory:1520 kb
****************************************************************/