HDU 3791 二叉搜索树(BST)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3791

       直接按第一个序列建二叉搜索树，然后接下来每一个需要判断的字符串都要建一个二叉搜索树，然后遍历一遍判断两个二叉搜索树是否相同就好了，需要注意的是最后遍历二叉搜索树的数据范围。

AC代码：

#include <bits/stdc++.h>
#define maxn 10005
using namespace std;
string str;
int a[maxn], b[maxn];
int n;

void insert(int x, int pre[]){
  int cnt = 1;
  while(pre[cnt] != -1){
    if(pre[cnt] >= x){
      cnt = (cnt << 1);
    }
    else cnt = (cnt << 1 | 1);
  }
  pre[cnt] = x;
  return ;
}

void Build(string s, int pre[]){
  pre[1] = (s[0] - '0');
  int len = s.length();
  for(int i=1;i<len;i++){
    insert(s[i] - '0', pre);
  }
  return ;
}

int main()
{
  while(~scanf("%d", &n)){
    if(n == 0) break;
    cin>>str;
    memset(a, -1, sizeof(a));
    Build(str, a);
    while(n--){
      cin>>str;
      memset(b, -1, sizeof(b));
      Build(str, b);
      bool flag = true;
      int len = str.length();
      for(int i=0;i<=10000;i++){
        if(a[i] != b[i]){
          flag = false;
          break;
        }
      }
      if(flag) puts("YES");
      else puts("NO");
    }
  }
  return 0;
}