题解 | #二叉搜索树#

#include<cstdio>
#include<string>
using namespace std;

struct TreeNode {
    char data;
    TreeNode* LChild;
    TreeNode* RChild;
};

void InSertBSTTree(TreeNode*& root, char  data ) {
    TreeNode* pa = new TreeNode;
    pa->data = data;
    pa->LChild = NULL;
    pa->RChild = NULL;
    if (root == NULL) {
        root = pa;
    } else {
        TreeNode* ppre = root;
        TreeNode* pcur;
        while (true) {
            if (data < ppre->data) {
                pcur = ppre->LChild;
                if (pcur == NULL) {
                    ppre->LChild = pa;
                    break;
                } else {
                    ppre = pcur;
                }
            } else {
                pcur = ppre->RChild;
                if (pcur == NULL) {
                    ppre ->RChild = pa;
                    break;
                } else {
                    ppre = pcur;
                }
            }
        }

    }

}
string MidOrder( TreeNode* root) {
    if (root == NULL) {
        return "";
    }
    return MidOrder(root->LChild) + root->data + MidOrder(root->RChild);

}
string PreOrder( TreeNode* root) {
    if (root == NULL) {
        return "";
    }
    return root->data + PreOrder(root->LChild)  + PreOrder(root->RChild);

}
int main() {
    int n;
    while (scanf("%d", &n) != EOF) {
        if (0 == n ) {
            break;
        }
        char str1[100];
        scanf("%s", str1);
        TreeNode* root1 = NULL;
        for (int i = 0 ; str1[i] != '\0'; ++i) {
            InSertBSTTree(root1, str1[i]);
        }
        string PreOrder1 = PreOrder((root1));
        string MidOrder1 = MidOrder((root1));
//        printf("%s %s",PreOrder1.c_str(),MidOrder1.c_str());
        char str2[100];
        for (int idx = 0 ; idx<n; ++idx){
        scanf("%s", str2);
        TreeNode* root2 = NULL;
        for (int i = 0 ; str2[i] != '\0'; ++i) {
            InSertBSTTree(root2, str2[i]);
        }
        string PreOrder2 = PreOrder((root2));
        string MidOrder2 = MidOrder((root2));
        if (PreOrder2 == PreOrder1 && MidOrder1 == MidOrder2) {
            printf("YES\n");
        } else {
            printf("NO\n");
        }
    }
    }

}