题解 | 二叉搜索树

#include <iostream>
#include <string>

using std::cout;
using std::cin;
using std::endl;
using std::string;

struct TNode {
    char data;
    TNode* lchild;
    TNode* rchild;
};

void Insert(TNode*& root, char key) {
    if (root == nullptr) {
        root = new TNode();
        root->data = key;
        root->lchild = nullptr;
        root->rchild = nullptr;
        return;
    }
    if (key <= root->data) {
        Insert(root->lchild, key);
    } else {
        Insert(root->rchild, key);
    }
}

bool flag = true;   // 标识两棵树是否相同
// 先序遍历判断两颗树是否相同
void cmp(TNode* root1, TNode* root2) {
    if (root1 == nullptr && root2 == nullptr)
        return;
    if (root1 == nullptr || root2 == nullptr ||
            root1->data != root2->data) {
        flag = false;
        return;
    }
    cmp(root1->lchild, root2->lchild);
    cmp(root1->rchild, root2->rchild);
}

void destroy(TNode* root) {
    if (root) {
        destroy(root->lchild);
        destroy(root->rchild);
        delete root;
    }
}

int main() {
    int n;
    cin >> n;
    TNode* root = nullptr;// 模型书根节点
    //  获取初始序列
    string str;
    cin >> str;
    //  根据初始序列构建模型树
    for (auto ele : str)
        Insert(root, ele);
    for (int i = 0; i < n; ++i) {
        TNode* toCmp = nullptr;// 比较树的根节点
        //  输入待比较的序列
        string str2;
        cin >> str2;

        // 若两个序列长度不一样,则树必不相同
        if (str.size() != str2.size()) {
            cout << "NO" << endl;
            continue;
        }

        //  根据str2建树
        for (auto ele : str2) {
            Insert(toCmp, ele);
        }
        flag = true;
        cmp(root, toCmp);
        if (flag)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
        destroy(toCmp);
    }
    destroy(root);
    root = nullptr;

    return 0;
}