浙江财经大学
信息管理与工程学院

HDU 3791 二叉查找树

本文由 Ocrosoft 于 2016-05-10 22:29:36 发表

二叉搜索树

    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
 

Source

浙大计算机研究生复试上机考试-2010年


Solution

二叉树的应用,WA了7次,一直以为是树的内容写错了,最后改得实在是没地方可以改了…最后发现,读入的方法不对…

一开始读入是读一个n,然后读两个字符串,最后用while(cin>>c)以字符串形式读入多余数据,以0和长度为1结束,不对。

正确的读入应该是,while(cin>>n&&n),也就是多余数据用int来保存。

Code(AC)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <cstring>
#define ms(a) memset(a,0,sizeof(a))
#define mss(a) memset(a,-1,sizeof(a))
using namespace std;
//1+2+4+8+16+32+64+128+256+512=1023
int a[1024],b[1024];
void build(int d[],int pos,int t)
{
    if(d[pos]==-1)
    {d[pos]=t;return;}
    if(t<d[pos])build(d,pos*2,t);
    else build(d,pos*2+1,t);
    /*这个代码不需要pos,占用内存更少
    int now=1;
    while(d[now]!=-1)
    if(d[now]<t)now=now*2+1;
    else now=now*2;
    d[now]=t;
    */
}
int  main()
{
    int n;
    char c[12];
    while(cin>>n&&n)
    {
        mss(a);
        cin>>c;
        for(int i=0,len=strlen(c); i<len; i++)
        build(a,1,c[i]-'0');
        for(int i=0;i<n;i++)
        {
            mss(b);
            cin>>c;
            for(int i=0,len=strlen(c); i<len; i++)
            build(b,1,c[i]-'0');
            int j;
            for(j=0; j<1024; j++)
            if(a[j]!=b[j])break;
            if(j==1024)printf("YES\n");
            else printf("NO\n");
        }
    }
    return 0;
}

 

欢迎分享与转载,请保留链接与出处。Ocrosoft » HDU 3791 二叉查找树

点赞 (0)or拍砖 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址