题解 | 二叉搜索树

#include <iostream>
#include <string>
using namespace std;
string s, r;
typedef struct tree {
    int d;
    struct tree* l, *r;
}* T;
tree* fun(tree* t, int val) { //构建搜索树
    if (t == NULL) {
        tree* g = new tree();
        g->d = val;
        g->l = nullptr;
        g->r = nullptr;
        return g;
    }
    if (val < t->d)t->l = fun(t->l, val);
    if (val > t->d)t->r = fun(t->r, val);
    return t;
}
void preorder(tree* t, string& s) {
    if (t == nullptr)return ;
    //cout << t->d << " ";
    //return t->d;
    s = s + to_string(t->d);
    preorder(t->l, s);
    preorder(t->r, s);
}
void inorder(tree* t, string& s) {
    if (t == nullptr)return;
    inorder(t->l, s);
    s = s + to_string(t->d);
    inorder(t->r, s);
    //cout << t->d << " ";
    //return t->d;
}
int main() {
    int n;
    while (cin >> n) {
        if (n == 0)break;
        cin >> s;
        tree* sr = nullptr;
        for (int i = 0; i < s.size(); i++)sr = fun(sr, s[i] - '0');
        string pre1, in1;
        preorder(sr, pre1);
        inorder(sr, in1);
        while (n--) {
            cin >> r;
            int i = 0;

            tree* tr = nullptr;
            for (int i = 0; i < r.size(); i++)tr = fun(tr, r[i] - '0');
            string pre2, in2;
            preorder(tr, pre2);
            inorder(tr, in2);
            //if (preorder(sr) != preorder(tr))cout << "NO";
            if (pre1 == pre2 && in1 == in2)cout << "YES" << endl;
            else cout << "NO" << endl;
        }
    }
}