题解 | #二叉搜索树#

#include <iostream>
using namespace std;
int n;
string s1;
//树
struct Tnode {
    char data;
    Tnode* l, * r;
};
//将字符插入树
void insert(Tnode*& root, char x) {
    if (root->l == NULL && x < root->data) {
        Tnode* newnode = new Tnode;
        newnode->data = x;
        newnode->l = newnode->r = NULL;
        root->l = newnode;
    } else if (root->r == NULL && x > root->data) {
        Tnode* newnode = new Tnode;
        newnode->data = x;
        newnode->l = newnode->r = NULL;
        root->r = newnode;
    } else if (x > root->data) {
        insert(root->r, x);
    } else if (x < root->data) {
        insert(root->l, x);
    }
}
//利用字符串建立一棵树
Tnode* create(string s) {
    //来一个根节点
    Tnode* root = new Tnode;
    root->data = s[0];
    root->l = root->r = NULL;
    //处理子孙
    for (int i = 1; i < s.length(); i++) {
        insert(root, s[i]);
    }
    return root;
}
//比较两棵树是否一样
bool my_compare(Tnode* a, Tnode* b) {
    if (a == NULL && b == NULL) return true;
    if (a == NULL || b == NULL) return false;
    //比较这个节点值一不一样
    if (a->data != b->data) return false;
    return my_compare(a->l, b->l) && my_compare(a->r, b->r);
}
int main() {
    while (cin >> n) {
        cin >> s1;
        //给模板串建立一棵树
        Tnode* m = create(s1);
        for (int i = 0; i < n; i++) {
            cin >> s1;
            Tnode* n = create(s1);
            //比较两棵树
            if (my_compare(m, n)) cout << "YES" << endl;
            else cout << "NO" << endl;
        }
    }
}
// 64 位输出请用 printf("%lld")