题目描述

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

输入描述:

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

输出描述:

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

示例1

输入

2
567432
543267
576342
0

输出

YES
NO

代码

#include<iostream>
#include<cstdio>
using namespace std;
struct TreeNode{
    int data;
    TreeNode* leftChild;
    TreeNode* rightChild;
    TreeNode(int x)
    {
        data=x;
        leftChild=NULL;
        rightChild=NULL;
    }
};

TreeNode* Insert(TreeNode* root,int x)
{
    if(root==NULL)
    {
        root=new TreeNode(x);
    }
    else if(x<root->data)
        root->leftChild=Insert(root->leftChild,x);
    else if(x>root->data)
        root->rightChild=Insert(root->rightChild,x);
    return root;
}
bool IfSame(TreeNode* root,TreeNode* root1)
{
    if(root==NULL && root1==NULL)
        return true;
    else if(root->data==root1->data)
        return IfSame(root->leftChild,root1->leftChild) && IfSame(root->rightChild,root1->rightChild);
    else
        return false;
}

int main()
{
    string str;
    string s;
    int n;
    while(cin>>n)
    {
        if(n==0)
            break;
        cin>>str;
        TreeNode* root=NULL;
        for(int i=0;i<str.size();i++)
        {
            int b=str[i]-'0';
            root=Insert(root,b);
        }
        while(n--)
        {
            cin>>s;
            TreeNode* root1=NULL;
            for(int i=0;i<s.size();i++)
            {
                int a=s[i]-'0';
                root1=Insert(root1,a);
            }
            if(IfSame(root,root1))
                cout<<"YES"<<endl;
            else
                cout<<"NO"<<endl;
        }
    }
    return 0;
}