构建二叉搜索树，比较树相同

先建树，通过insert()插入节点。
二叉搜索树的递归建立的过程如下:

插入代码：

TreeNode *BuildTree(TreeNode *root,int x){
    if(root==NULL)
        root=new TreeNode(x);
    else if(root->val<x)
        root->right=BuildTree(root->right,x);
    else if(root->val>x)
        root->left=BuildTree(root->left,x);
    return root;
}

然后判断两树是否相等？
可以遍历前序，如果不相等则不同。也可以直接递归比较两树子树。
给出第二种方法：

bool is_equal(TreeNode *x,TreeNode *y){
    if(x==NULL && y==NULL)return true;
    else if(x==NULL&&y!=NULL || x!=NULL&&y==NULL)return false;
    if(x->val!=y->val)return false;
    return is_equal(x->left,y->left) && is_equal(x->right,y->right);
}

总代码：

#include<iostream>
#include<string>
using namespace std;
struct Node{
    char val;
    Node *left;
    Node *right;
    Node(char cc):val(cc),left(NULL),right(NULL){}
}; 
Node *insert(Node *root,char c){
    if(root==NULL){
        return new Node(c);
    }
    if(root->val>c){
        root->left=insert(root->left,c);
    }else{
        root->right=insert(root->right,c);
    }
    return root;
}
bool is_same1(Node *root1,Node *root2){
    if(root1==NULL&&root2==NULL)return true;
    if(root1!=NULL&&root2==NULL || root1==NULL&&root2!=NULL || root1->val!=root2->val){
        return false;
    }
    return is_same1(root1->left,root2->left)&&is_same1(root1->right,root2->right);
}
int main(){
    int n;
    string s,t;
    while(cin>>n){
        if(n==0)break;
        cin>>s;
        Node *root1=NULL;
        for(int i=0;i<s.size();i++){
            root1=insert(root1,s[i]);
        }
        for(int i=0;i<n;i++){
            cin>>t;
            Node *root2=NULL;
            for(int j=0;j<t.size();j++){
                root2=insert(root2,t[j]);
            }
            if(is_same1(root1,root2)){
                cout<<"YES"<<endl;
            }else cout<<"NO"<<endl;
        }
    }

    return 0;
}