1737: 二叉搜索树

解题思路:

注意事项:

参考代码:

#include<bits/stdc++.h>
using namespace std;
struct Node{
    char val;
    Node* cl;
    Node* cr;
};
//建树
void creatTree(Node** T,char data){
    if(*T==NULL){
        Node* node=new Node;
        node->val=data;
        node->cl=NULL;
        node->cr=NULL;
        *T=node;
    }
    else{
        if(data > (*T)->val) creatTree((&(*T)->cr),data);
        else if(data < (*T)->val) creatTree((&(*T)->cl),data);
    }
    return;
}
//获取前中后序列
void dfs(Node* T,string& s,int x){
    if(x==1){
        if(T!=NULL){
            s+=T->val;
            dfs(T->cl,s,x);
            dfs(T->cr,s,x);
        }
    }else if(x==2){
        if(T!=NULL){
            dfs(T->cl,s,x);
            s+=T->val;
            dfs(T->cr,s,x);
        }
    }else if(x==3){
        if(T!=NULL){
            dfs(T->cl,s,x);
            dfs(T->cr,s,x);
            s+=T->val;
        }
    }
}

vector<string> getorder(Node* T){
    string a,b,c;
    dfs(T,a,1);//pre
    dfs(T,b,2);//mid
    dfs(T,c,3);//last
    vector<string>arr;
    arr.push_back(a);
    arr.push_back(b);
    arr.push_back(c);
    return arr;
}

int main()
{
    int n;
    while(cin>>n){
        if(n==0) return 0;
        string s;
        cin>>s;
        Node* T=NULL;
        for(auto &k:s){
            creatTree(&T,k);
        }
        vector<string>arr;
        arr=getorder(T);
        while(n--){
            string st;
            cin>>st;
            Node* newT=NULL;
            for(auto &k:st){
                creatTree(&newT,k);
            }
            vector<string>t;
            t=getorder(newT);
            if(t==arr) cout<<"YES\n";
            else cout<<"NO\n";
            
        }
    }
    return 0;
}