[C++知识库]【牛客网】KY124 二叉搜索树

判断是否为同一二叉搜索树，首先就是要构造成二叉搜索树，则若是数据是一样的，那么中序遍历一定是一样的，因此中序遍历无法判断是否为同一二叉搜索树，但是其他遍历方式如先序遍历、后序遍历和层序遍历，则都能够判断，因此我采用的是先序遍历进行判断：

#include<iostream>
#include<string>

using namespace std;

struct TreeNode{
    int data;
    struct TreeNode *lchild, *rchild;
    TreeNode(int d): data(d), lchild(nullptr), rchild(nullptr){}
};

TreeNode* insert(TreeNode *root, int x){
    if(root == nullptr) root = new TreeNode(x);
    else if(x < root->data) root->lchild = insert(root->lchild, x);
    else if(x > root->data) root->rchild = insert(root->rchild, x);
    return root;
}

bool judge(TreeNode *root, TreeNode *root1){
    if(root == nullptr && root1 == nullptr) return true;
    if(root->data != root1->data) return false;
    else return judge(root->lchild, root1->lchild) && judge(root->rchild, root1->rchild);
}

int main(){
    int n;
    string str, str1;
    while(scanf("%d", &n) != EOF){
        if(n == 0) break;
        cin>>str;
        int k = str.size();
        TreeNode *root = nullptr;
        for(int i = 0;i < k;i++) root = insert(root, str[i] - '0');
        while(n--){
            cin>>str1;
            k = str1.size();
            TreeNode *root1 = nullptr;
            for(int i = 0;i < k;i++) root1 = insert(root1, str1[i] - '0');
            if(judge(root, root1)) printf("YES\n");
            else printf("NO\n");
        }
    }
    return 0;
}