题解 | #二叉搜索树#双指针建二叉搜索树

#include "cstdio"
#include "string"

using namespace std;

struct TreeNode {
    char data;
    struct TreeNode* left;
    struct TreeNode* right;
};

void insertBST(TreeNode*& root, int data) {
    TreeNode* node = new TreeNode;
    node->data = data;
    node->left = node->right = NULL;

    if (NULL == root) {
        root = node;
    } else {
        TreeNode* pre = root, *cur;
        while (true) {
            if (data < pre->data) {
                cur = pre->left;
                if (NULL == cur) {
                    pre->left = node;
                    break;
                } else {
                    pre = cur;
                }
            } else {
                cur = pre->right;
                if (NULL == cur) {
                    pre->right = node;
                    break;
                } else {
                    pre = cur;
                }
            }
        }
    }
}

string preOrder(TreeNode* root) {
    if (NULL == root)
        return "";
    return root->data + preOrder(root->left) + preOrder(root->right);
}

string  inOrder(TreeNode* root) {
    if (NULL == root)
        return "";
    return inOrder(root->left) + root->data + inOrder(root->right);
}

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) {
            insertBST(root1, str1[i]);
        }
        string preOrder1 = preOrder(root1);
        string inOrder1 = inOrder(root1);
//        printf("%s\n", preOrder1.c_str());
//        printf("%s\n", inOrder1.c_str());

        for (int i = 0; i < n; ++i) {
            char str2[100];
            scanf("%s", str2);
            TreeNode* root2 = NULL;
            for (int i = 0; str2[i] != '\0'; ++i) {
                insertBST(root2, str2[i]);
            }
            string preOrder2 = preOrder(root2);
            string inOrder2 = inOrder(root2);
//            printf("%s\n", preOrder2.c_str());
//            printf("%s\n", inOrder2.c_str());
            if (preOrder1 == preOrder2 && inOrder1 == inOrder2) {
                printf("YES\n");
            } else {
                printf("NO\n");
            }
        }

    }
    return 0;
}