题解 | #二叉搜索树#

//注意循环for(idx++.不是N++）
//注意root2,尽管root2替换为空指针了，但是还是要free掉
#include <cstdio>
#include <vector>
#include <string>
using namespace std;

struct Tree { // Tree data structure
    char data;
    Tree* left;
    Tree* right;

    Tree(char data) {
        this->data = data;
        this->left = NULL;
        this->right = NULL;
    }
};

void insertBST(int data, Tree*& root) {
    if (root == NULL) {
        root = new Tree(data);
        return;
    }

    Tree* pCur = root;
    while (true) {
        if (data < pCur->data) {
            if (pCur->left == NULL) {
                pCur->left = new Tree(data);
                break;
            }
            pCur = pCur->left;
        }
        else {
            if (pCur->right == NULL) {
                pCur->right = new Tree(data);
                break;
            }
            pCur = pCur->right;
        }
    }
}

string Inorder(Tree* root) {
    if (root == NULL) {
        return "";
    }
    else return Inorder(root->left) + root->data + Inorder(root->right);
}

string Preorder(Tree* root) {
    if (root == NULL) {
        return "";
    }
    else return root->data + Preorder(root->left) + Preorder(root->right);
}

int main() {
    int n;
    while (scanf("%d", &n) != EOF) {
        if (n == 0) {
            break;
        }

        char str1[100];
        scanf("%s", str1);
        Tree* root1 = NULL;
        for (int i = 0; str1[i] != '\0'; i++) {
            insertBST(str1[i], root1);
        }

        string mid1 = Inorder(root1);
        string pre1 = Preorder(root1);

        char str2[100];
        for (int idx = 0; idx < n; idx++) {
            scanf("%s", str2);
            Tree* root2 = NULL;
            for (int i = 0; str2[i] != '\0'; i++) {
                insertBST(str2[i], root2);
            }

            string mid2 = Inorder(root2);
            string pre2 = Preorder(root2);
            if (mid1 == mid2 && pre1 == pre2) {
                printf("YES\n");
            }
            else {
                printf("NO\n");
            }

            // Free memory
            delete root2;
        }


    }

    return 0;
}