题解 | #二叉搜索树#

#include "cstdio"
#include <string>
using namespace std;
struct TreeNode{
    char data;
    TreeNode * leftChild;
    TreeNode * rightChild;
};
void insertBST(TreeNode * &root, char data){
    TreeNode * treeNode =new TreeNode;
    treeNode->data = data;
    treeNode->leftChild=NULL;
    treeNode->rightChild=NULL;
    if (root==NULL){
        root=treeNode;
    } else{
        TreeNode * father = root;//待插入结点的父亲
        TreeNode * jie;
        while (true){
            if (data< father->data){
                jie = father->leftChild;
                if (jie == NULL){
                    father->leftChild=treeNode;
                    break;
                } else{
                    father=jie;
                }
            } else{
                jie=father ->rightChild;
                if (jie==NULL){
                    father->rightChild = treeNode;
                    break;
                } else{
                    father = jie;
                }
            }
        }
    }
}
string preOrder(TreeNode *root){
    if (root==NULL){
        return "" ;
    }
    return root->data+preOrder(root->leftChild)+preOrder(root->rightChild);
}

string InOrder(TreeNode *root){
    if (root==NULL){
        return "";
    }
    return InOrder(root->leftChild)+root->data+InOrder(root->rightChild);
}
int main(){
    int n;
    while (scanf("%d",&n)!=EOF){
        if (n==0){
            break;
        }
        char arr[100];
        scanf("%s",arr);
        TreeNode * root1 = NULL;
        for (int i = 0; arr[i]!='\0' ; ++i) {
            insertBST(root1,arr[i]);
        }
        string preOrder1 = preOrder(root1);
        string inOrder1 = InOrder(root1);
//        printf("%s %s",preOrder1.c_str(),inOrder1.c_str());
        char arr2[100];
        for (int i1 = 0; i1 < n; ++i1) {
            scanf("%s",arr2);
            TreeNode *root2 = NULL;
            for (int i = 0; arr2[i] !='\0' ; ++i) {
                insertBST(root2,arr2[i]);

            }
            string preOrder2 = preOrder(root2);
            string inOrder2 = InOrder(root2);
            if (preOrder1==preOrder2 && inOrder1==inOrder2){
                printf("YES\n");
            }else{
                printf("NO\n");
            }
        }
    }

}