题解 | #二叉搜索树#

用Insert函数构建二叉搜索树，判断时同样再构建一个树，分别对其前序遍历，判断遍历序列是否相等

#include <iostream>
using namespace std;

struct TreeNode{
    char s_data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(char num)
    {
        this->s_data = num;
        this->left = NULL;
        this->right = NULL;
    }
};

string RootStr;          //初始树前序序列
string currentStr;          //判断树前序序列

TreeNode *Insert(TreeNode *root,char data)
{
    if(root ==NULL)
    {
        root = new TreeNode(data);
    }else if(data>root->s_data)
    {
        root->right = Insert(root->right,data);
    } else
    {
        root->left = Insert(root->left,data);
    }
    return root;
}

void PreOrder(TreeNode *root,string &str)
{
    if(root==NULL)
    {
        return;
    } else
    {
        str.push_back(root->s_data);
        PreOrder(root->left,str);
        PreOrder(root->right,str);
    }
    return;
}

int main(){
    int n;
    string str;
    while (cin>>n)
    {
        cin.ignore();
        if(n==0)
        {
            break;
        }
        //建树初始树
        TreeNode *root = NULL;
        getline(cin,str);
        for(int i=0;i<str.size();i++)
        {
            root = Insert(root,str[i]);
        }
        PreOrder(root,RootStr);
        //判断
        for(int i=0;i<n;i++)
        {
            TreeNode *current = NULL;
            getline(cin,str);
            for(int i=0;i<str.size();i++)       //构建判断的树
            {
                current = Insert(current,str[i]);
            }
            currentStr.clear();
            PreOrder(current,currentStr);
            if(currentStr == RootStr)
            {
                cout<<"YES"<<endl;
            } else
            {
                cout<<"NO"<<endl;
            }
        }
    }
    return 0;
}