题解 | 二叉搜索树

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

struct Tnode{
    int data;
    struct Tnode* left;
    struct Tnode* right;
    Tnode(int i):data(i),left(nullptr),right(nullptr){}
};

Tnode* insert(Tnode* t,int x){
    if(t==nullptr)t=new Tnode(x);
    else if(x<t->data)t->left=insert(t->left,x);
    else t->right=insert(t->right,x);
    return t;
}
string s="";
void preOrder(Tnode* t){
    if(t==nullptr)return;
    char c=t->data+'0';
    s=s+c;
    preOrder(t->left);
    preOrder(t->right);
}

void inOrder(Tnode* t){
    if(t==nullptr)return;
    inOrder(t->left);
    char c=t->data+'0';
    s=s+c;
    inOrder(t->right);
}

struct cp{
    string pre;
    string in;
    cp(string pre,string in):pre(pre),in(in){}
};

int main(){
    int n;
    while(cin>>n){
        if(n==0)break;
        std::vector<Tnode*> a;
        for(int i=0;i<=n;i++){
            string s;
            Tnode* t=nullptr;
            cin>>s;
            for(int i=0;i<s.size();i++){
                t=insert(t,s[i]-'0');
            }
            a.push_back(t);
        }
        vector<cp> b;
        for(int i=0;i<a.size();i++){
            s="";
            preOrder(a[i]);
            string t=s;
            s="";
            inOrder(a[i]);
            b.push_back(cp(t,s));
        }
        for(int i=1;i<b.size();i++){
            if(b[0].pre==b[i].pre&&b[0].in==b[i].in)cout<<"YES"<<endl;
            else cout<<"NO"<<endl;
        }
    }
}

既然实现了插入，那么难点就剩下了如何判断是否相同，其实根据算法原理，我们可以知道，只要一个树的前中序相同，那么必然是一个树，那么我们可以用一个cp来存这俩的string形式，然后直接判断这俩是否都一样即可