题解 | #二叉搜索树#

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

typedef struct BTreeNode {
    int data;
    struct BTreeNode* lchild;
    struct BTreeNode* rchild;
} BTreeNode, *BTree;

BTreeNode* create(int data) {
    BTreeNode* root = (BTreeNode*)malloc(sizeof(BTreeNode));
    root->data = data;
    root->lchild = NULL;
    root->rchild = NULL;
    return root;
}

BTreeNode* Insert(BTreeNode* root, int x) {
    if (root == NULL) {
        return create(x);
    } else if (root->data > x) {
        root->lchild = Insert(root->lchild, x);
    } else if (root->data < x) {
        root->rchild = Insert(root->rchild, x);
    }
    return root;
}

bool isSameBST(BTreeNode* root1, BTreeNode* root2) {
    // 如果两个节点都是空节点，那么它们被认为是相同的（空树与空树相同）
    if (root1 == NULL && root2 == NULL) {
        return true;
    }
    // 如果其中一个节点为空，而另一个节点不为空，那么它们一定不同
    if (root1 == NULL || root2 == NULL) {
        return false;
    }
    // 如果两个节点都不为空，但是它们的数据值不同，那么它们一定不同
    if (root1->data != root2->data) {
        return false;
    }
    // 如果两个节点都不为空且数据值相同，那么递归地比较它们的左子树和右子树
    // 只有当左子树和右子树都相同时，这两个节点才被认为是相同的
    return isSameBST(root1->lchild, root2->lchild) &&
           isSameBST(root1->rchild, root2->rchild);
}

bool buildAndCompare(char* seq1, char* seq2, int len) {
    BTree root1 = NULL, root2 = NULL;
    for (int i = 0; i < len; i++) {
        root1 = Insert(root1, seq1[i] - '0');
    }
    for (int i = 0; i < len; i++) {
        root2 = Insert(root2, seq2[i] - '0');
    }
    return isSameBST(root1, root2);
}

int main() {
    int n;
    while (scanf("%d", &n) != EOF && n != 0) {
        char seq1[11];
        scanf("%s", seq1);
        int len = strlen(seq1);
        while (n--) {
            char seq2[11];
            scanf("%s", seq2);
            if (buildAndCompare(seq1, seq2, len)) {
                printf("YES\n");
            } else {
                printf("NO\n");
            }
        }
    }
    return 0;
}