题解 | #二叉搜索树#

无论插入的序列如何，中序遍历必定是递增序列，所以是相同的。所以只需要判断前序或后续遍历序列。

#include <iostream>
using namespace std;
struct node {
    char data;
    node* leftChild;
    node* rightChild;
    node(char a) {
        data = a;
        leftChild = NULL;
        rightChild = NULL;
    }
};
string preOrderStr;
node* insert(node* root, char a) {
    if (root == NULL) {
        return new node(a);
    }
    if (a < root->data) root->leftChild = insert(root->leftChild, a);
    else root->rightChild = insert(root->rightChild, a);

    return root;
}
void preOrder(node* root) {
    if (root == NULL) return;
    preOrderStr += root->data;
    preOrder(root->leftChild);
    preOrder(root->rightChild);
}
int main() {
    int n;
    while (cin >> n) { // 注意 while 处理多个 case
        if (n == 0) break;
        string old;
        cin>>old;
        node* oldRoot=NULL;
        for (int i = 0; i < old.size(); i++) {
            oldRoot = insert(oldRoot, old[i]);
        }
        preOrderStr.clear();
        preOrder(oldRoot);
        string preOrderStrOld = preOrderStr;
        while (n--) {
            string newStr;
            cin>>newStr;
            node* newRoot=NULL;
            for (int i = 0; i < old.size(); i++) {
                newRoot = insert(newRoot, newStr[i]);
            }
            preOrderStr.clear();
            preOrder(newRoot);
            if(preOrderStrOld==preOrderStr) cout<<"YES"<<endl;
            else cout<<"NO"<<endl;
        }
    }
}
// 64 位输出请用 printf("%lld")