首页 > 其他 > 详细

HDU 3791

时间:2019-08-30 21:28:54      阅读:66      评论:0      收藏:0      [点我收藏+]

二叉搜索树

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 8507    Accepted Submission(s): 3814


Problem Description
判断两序列是否为同一二叉搜索树序列
 

 

Input
开始一个数n,(1<=n<=20) 表示有n个需要判断,n= 0 的时候输入结束。
接下去一行是一个序列,序列长度小于10,包含(0~9)的数字,没有重复数字,根据这个序列可以构造出一颗二叉搜索树。
接下去的n行有n个序列,每个序列格式跟第一个序列一样,请判断这两个序列是否能组成同一颗二叉搜索树。
 

 

Output
如果序列相同则输出YES,否则输出NO
 

 

Sample Input
2
567432
543267
576342
0
 

 

Sample Output
YES
NO
 
题意:开始一个数n,(1<=n<=20) 表示有n个需要判断,n= 0 的时候输入结束。
接下去一行是一个母序列,序列长度小于10,包含(0~9)的数字,没有重复数字,根据这个序列可以构造出一颗二叉搜索树。
接下去的n行有n个子序列,每个序列格式跟第一个序列一样,请判断这两个序列是否能组成一颗相同的二叉搜索树。
 
#include<iostream>
#include<string.h>
#include<string>
#include<algorithm>
#include<math.h>
#include<string>
#include<string.h>
#include<vector>
#include<utility>
#include<map>
#include<queue>
#include<set>
#define mx 0x3f3f3f3f
#define ll long long
#define MAXN 100
using namespace std;
int tree[10005],a[10005];
int tree1[10005];

void insert()//二叉树建树
{
    memset(tree,-1,sizeof(tree));
    for(int i=0;a[i];i++)
    {
        int num=a[i]-0;
        int j=1;
        while(tree[j]!=-1)
        {
            if(num>tree[j])
                j=j*2;
            else
                j=j*2+1;
        }
        tree[j]=num;
    }

}
int main()
{
    int n;
    while(cin>>n){
    if(n==0)
        break;
    string s;
    cin>>s;
    memset(tree,-1,sizeof(tree));
    for(int i=0;s[i];i++)
    {
        int num=s[i]-0;
        int j=1;
        while(tree[j]!=-1)
        {
            if(num<tree[j])
                j=j*2;
            else
                j=j*2+1;
        }
        tree[j]=num;
    }
    
    while(n--)
    {
        string ss;
        cin>>ss;
        memset(tree1,-1,sizeof(tree1));
        for(int i=0;ss[i];i++)
        {
            int num=ss[i]-0;
            int j=1;
            while(tree1[j]!=-1)
            {
                if(num<tree1[j])
                    j=j*2;
                else
                    j=j*2+1;
            }
            tree1[j]=num;
        }
        int i;
        for(i=1;i<=1024&&tree[i]==tree1[i];i++);
        if(i>1024)
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
        
    }
}
    return 0;

}

 

HDU 3791

原文:https://www.cnblogs.com/-citywall123/p/11436554.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!