HDU3791(解题报告)

2024-09-07 20:32

文章标签 报告解题 hdu3791

本文主要是介绍HDU3791(解题报告)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

二叉搜索树

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

Problem Description

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

Input

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

Output

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

Sample Input

Sample Output

  YES
NO
解题思路：
本题大意是先输入样例个数，第二行给出标准二叉搜索树，接下来n行输入，每次判断输入与标准二叉搜索树是否吻合。
所谓二叉搜索树，就是左海子 < 根节点 < 右孩子的一棵树。s存每次输入的字符串，t1存标准输入的搜索树，t2存
样例输入的树。个人感觉最神奇的地方在于建树那，即inset函数，初始化t1,t2后，如果t[pos]!=-1,则会判断t[pos]
和c（即s[i]所对应的数字）的大小，如果t[pos]<c,则搜索右孩子，即pos=pos*2+1,反之，搜索左孩子,pos=pos*2。
总之，先把标准二叉搜索树建起来，接下来每次输入也建起树来，循环遍历比较，如果一模一样，则输出YES，否则输出NO。
解题代码：
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define INF 10000
char s[INF];
int t1[INF];
int t2[INF];void inset(char w,int *t)
{int pos=1;int c=w-'0';while(t[pos]!=-1){if(t[pos]<c)pos=2*pos+1;elsepos=2*pos;}t[pos]=c;
}void build(char *str,int *t)
{t[1]=str[0]-'0';for(int i=1;s[i];i++)inset(s[i],t);
}int main()
{//freopen("in.txt","r",stdin);
    int n,i;while(scanf("%d",&n)!=EOF&&n){memset(t1,-1,sizeof(t1));scanf("%s",s);build(s,t1);while(n--){memset(t2,-1,sizeof(t2));scanf("%s",s);build(s,t2);for(i=0;i<5000;i++)if(t1[i]!=t2[i])break;if(i==5000)printf("YES\n");elseprintf("NO\n");}}return 0;
}