题解 | #二叉搜索树#

二叉排序树：左<根<右

• 相同元素的二叉排序树的中序遍历必定相同（升序）
• 先序遍历相同→元素相同（中序遍历相同）→二叉排序树相同

#include<iostream>
#include<string>
using namespace std;

struct node{
  int data;
  node* leftch;
  node* rightch;
  node(int x):data(x),leftch(nullptr),rightch(nullptr){}
};

node* insert(int a,node* root){//插入
  if(root==nullptr){
    root=new node(a);
    return root;
  }
  if(a>root->data){
    root->rightch=insert(a,root->rightch);
  }
  else if(a<root->data){
    root->leftch=insert(a,root->leftch);
  }
  return root;
}

bool preorder(node* root0,node* root1){//比较先序遍历
  if(root0==nullptr&&root1==nullptr)return true;//递归出口
  else if((root0==nullptr&&root1!=nullptr)||root1==nullptr&&root0==nullptr)return false;
  
  if(root0->data!=root1->data)return false;//比较当前结点数据
  return preorder(root0->leftch,root1->leftch)&&preorder(root0->rightch,root1->rightch);//递归
  
}

int main(){
  string s0,s1;
  int n;
  while(scanf("%d",&n)!=EOF){
    if(n==0)break;
    cin>>s0;
    node* root0=nullptr;
    for(int i=0;i<s0.size();i++){
      root0=insert(s0[i]-'0',root0);
    }
    
    for(int j=0;j<n;j++){
      cin>>s1;
      node* root1=nullptr;
      for(int i=0;i<s1.size();i++){
      root1=insert(s1[i]-'0',root1);
      }
      if(preorder(root0,root1))printf("YES\n");
      else printf("NO\n");
    }
  }
   
  return 0;
}