首页 > ACM题库 > HDU-杭电 > HDU 3791-二叉搜索树-二叉树-[解题报告]HOJ
2015
04-13

HDU 3791-二叉搜索树-二叉树-[解题报告]HOJ

二叉搜索树

问题描述 :

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

输入:

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

输出:

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

样例输入:

2
567432
543267
576342
0

样例输出:

YES
NO

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int tree1[10000];
int tree2[10000];
void Insert(char word,int *tree)
{
    int now=1;
    int c=word-'0';
    while(tree[now]!=-1)
    {
        if(tree[now]<c)
            now=now*2+1;
        else
            now=now*2;
    }
    tree[now]=c;
}
void build(char *str,int *tree)
{
    int l=strlen(str);
    int i=1;
    tree[1]=str[0]-'0';
    for(i=1;i<l;i++)
    {
        Insert(str[i],tree);
    }
}
int main()
{
    int n;
    char str[1000];
    while(scanf("%d",&n),n!=0)
    {
        memset(tree1,-1,sizeof(tree1));
        memset(tree2,-1,sizeof(tree2));
        scanf("%s",str);
        build(str,tree1);
        int i;
        for(i=0;i<n;i++)
        {
            memset(tree2,-1,sizeof(tree2));
            scanf("%s",str);
            build(str,tree2);
            int j;
            for(j=0;j<5000;j++)
            {
                if(tree1[j]!=tree2[j])
                    break;
            }
            if(j==5000)
                printf("YES\n");
            else
                printf("NO\n");
        }

    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/juststeps/article/details/8531940


  1. 有限自动机在ACM中是必须掌握的算法,实际上在面试当中几乎不可能让你单独的去实现这个算法,如果有题目要用到有限自动机来降低时间复杂度,那么这种面试题应该属于很难的级别了。

  2. a是根先忽略掉,递归子树。剩下前缀bejkcfghid和后缀jkebfghicd,分拆的原则的是每个子树前缀和后缀的节点个数是一样的,根节点出现在前缀的第一个,后缀的最后一个。根节点b出现后缀的第四个位置,则第一部分为四个节点,前缀bejk,后缀jkeb,剩下的c出现在后缀的倒数第2个,就划分为cfghi和 fghic,第3部分就为c、c