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 的时候输入结束。
接下去一行是一个序列,序列长度小于10,包含(0~9)的数字,没有重复数字,根据这个序列可以构造出一颗二叉搜索树。
接下去的n行有n个序列,每个序列格式跟第一个序列一样,请判断这两个序列是否能组成同一颗二叉搜索树。</div>

<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 条评论
  1. Timothyelaph

    301 Moved Permanently
    Click here...

    Timothyelaph 回复
发表新评论