HDU3791 二叉搜索树 - dblank

# HDU3791 二叉搜索树

<div class="panel_title" align="left">Problem Description</div>
<div class="panel_content">判断两序列是否为同一二叉搜索树序列</div>
<div class="panel_title" align="left">Input</div>
<div class="panel_content">开始一个数n，(1<=n<=20) 表示有n个需要判断，n= 0 的时候输入结束。

<div class="panel_title" align="left">Output</div>
<div class="panel_content">如果序列相同则输出YES，否则输出NO</div>
<div class="panel_title" align="left">Sample Input</div>
<div class="panel_content">
<div>2 567432</div>
<div>543267</div>
<div>576342 0</div>
</div>
<div class="panel_title" align="left">Sample Output</div>
<div class="panel_content">
<div>YES</div>
<div>NO</div>
</div>
<div class="panel_bottom"> 思路:二叉索引树的性质是左子树上的点都比根节点小，右子树上的点都比根节点大，按照这个性质，直接建树就好了，然后判断对应位置是否相同。</div>
<div class="panel_bottom">

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
using namespace std;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f, N = 100 + 10, Mod = 1000000009;
typedef long long ll;
char s[20];
int a[2000], b[2000];
int bfs()
{
queue<int> q;
q.push(1);
while(!q.empty())
{
int x  =q.front();
q.pop();
if(a[x] != b[x])
return 0;
if(a[x*2]!=-1 && x<=(1<<10))
q.push(x*2);
if(a[x*2+1]!=-1 && x<=(1<<10))
q.push(x*2+1);
}
return -1;
}
int main()
{
int n;
while(cin>>n)
{
memset(a, -1, sizeof(a));
memset(b, -1, sizeof(b));
scanf("%s", s);
a[1] = s[0] - '0';
for(int i = 1; s[i]; i++)
{
int id = 1, x = s[i] - '0';
while(a[id]!=-1)
{
if(x > a[id])
id = id*2 + 1;
else id*=2;
}
a[id] = x;
}
while(n--)
{
scanf("%s", s);
memset(b, -1, sizeof(b));
b[1] = s[0] - '0';

for(int i = 1; s[i]; i++)
{
int id = 1, x = s[i] - '0';
while(b[id]!=-1)
{
if(x > b[id])
id = id*2 + 1;
else id*=2;
}
b[id] = x;
}
puts(bfs()?"YES":"NO");
}
}
return 0;
}

</div>

### 相关文章

1. 301 Moved Permanently