题解 | #二叉搜索树#

本质核心还是 构建搜索树的代码 理解递归的思路即可

另外涉及到判断两个树是否相同的代码实现

也是可以递归实现 如果两结点值相同 再去判断这两个子树的左子树 和 这两个子树的右子树 是否也相同 递归去实现

如果两个节点都为空 返回true 二者有其一是null 返回false

#include <bits/stdc++.h>
#include <vector>
using namespace std;

struct TreeNode{
    char data;
    TreeNode*left;
    TreeNode*right;
    TreeNode(int val): data(val){}
};

vector<string> result;
string res;

void postTraverse(TreeNode* root){
    if(root == NULL) return ;
    postTraverse(root->left);
    postTraverse(root->right);
    res += root->data;
}

void orderTraverse(TreeNode* root){
    if(root == NULL) return ;
    postTraverse(root->left);
    res += root->data;
    postTraverse(root->right);
    
}

void firstTraverse(TreeNode* root){
    if(root == NULL) return ;
    res += root->data;
    postTraverse(root->left); 
    postTraverse(root->right);
    
}

void initial(TreeNode* root){
    res.clear();
    firstTraverse(root);
    result.push_back(res);
    res.clear();
    orderTraverse(root);
    result.push_back(res);
    res.clear();
    postTraverse(root);
    result.push_back(res);
    res.clear();
}

void insertTree(TreeNode* cur, TreeNode* root){
    if(root == NULL) return ;
    if(root->left == NULL && root->data > cur->data){
        root->left = cur;
        return;
    }
    if(root->right == NULL && root->data <= cur->data){
        root->right = cur;
        return;
    }
    if(root->data > cur->data) insertTree(cur, root->left);
    else insertTree(cur,root->right);
    return ;
}

bool judge(TreeNode* t1, TreeNode* t2){
    if(t1 == NULL && t2 == NULL) return  true;
    if(t1 == NULL && t2 != NULL) return  false;
    if(t2 == NULL && t1 != NULL) return  false;
    if(t1->data != t2->data) return false;
    if(!judge(t1->left, t2->left) || !judge(t1->right, t2->right)) return false;
    return true;;

}

int main() {
    int n;
    cin >> n;
    string str;
    cin >> str;
    TreeNode *root = new TreeNode(str[0]);
    for(int i = 1; i < str.size(); i++){
        TreeNode* cur = new TreeNode(str[i]);
        insertTree(cur,root);
    }
    // initial(root);
    while (n--) { // 注意 while 处理多个 case
        string temp;
        cin >> temp;
        TreeNode *rt = new TreeNode(temp[0]);
        for(int i = 1; i < temp.size(); i++){
           TreeNode* cur = new TreeNode(temp[i]);
           insertTree(cur,rt);
        }
        if(judge(rt, root)) cout << "YES";
        else cout << "NO";
        cout << endl;
    }
}
// 64 位输出请用 printf("%lld")