题解 | 二叉搜索树

#include <stdio.h>
#include <string>
using namespace std;

struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;
};
void InsertBST(TreeNode*& root, int data) {
    TreeNode* pNew = new TreeNode();
    pNew->data = data;
    pNew->left = NULL;
    pNew->right = NULL;
    if (root == NULL) {
        root = pNew;
    } else {
        TreeNode* curNode = root;
        TreeNode* prevNode ;
        while (1) {
            if (curNode->data > data) {
                prevNode = curNode;
                curNode = curNode->left;
                if (curNode == NULL) {
                    curNode = pNew;
                    prevNode->left = curNode;
                    break;
                }
            } else {
                prevNode = curNode;
                curNode = curNode->right;
                if (curNode == NULL) {
                    curNode = pNew;
                    prevNode->right = curNode;
                    break;
                }
            }
        }

    }
}
void PreOrder(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    printf("%d ", root->data);
    PreOrder(root->left);
    PreOrder(root->right);
}
void InOrder(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    InOrder(root->left);
    printf("%d", root->data);
    InOrder(root->right);
}
bool SameTree(TreeNode* root1, TreeNode* root2) {
    if (root1 == NULL && root2 == NULL) {
        return true;
    }
    if (root1 == NULL || root2 == NULL) {
        return false;
    }
    if (root1->data != root2->data) {
        return false;
    }
    return SameTree(root1->left, root2->left) &&
           SameTree(root1->right, root2->right);
}

int main() {
    int n;
    while (scanf("%d", &n) != EOF && n != 0) {
        char str[1000];
        scanf("%s", str);

        TreeNode* root = NULL;
        for (int i = 0; str[i] != '\0'; i++) {
            InsertBST(root, str[i] - '0');
        }
        for (int i = 0; i < n; i++) {
            char str1[1000];
            scanf("%s", str1);
            TreeNode* newRoot = NULL;
            for (int j = 0; str1[j] != '\0'; j++) {
                InsertBST(newRoot, str1[j] - '0');
            }

            if (SameTree(root, newRoot)) {
                printf("YES\n");
            } else {
                printf("NO\n");
            }
        }
    }

    return 0;
}