HDU3791 二叉搜索树【二叉搜索树】

本文主要是介绍HDU3791 二叉搜索树【二叉搜索树】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

二叉搜索树
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 9645 Accepted Submission(s): 4265

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年

问题链接：HDU3791 二叉搜索树
问题简述：（略）
问题分析：简单的二叉搜索树问题，不解释。
程序说明：（略）
参考链接：（略）
题记：（略）

AC的C++语言程序如下：

/* HDU3791 二叉搜索树 */#include <bits/stdc++.h>using namespace std;const int N = 10 + 1, M = 3000;
char s[N];
int tree1[M], tree2[M];void insert(char ch, int* tree)
{int cnt = 1;int x = ch - '0';while (tree[cnt] != -1)if (tree[cnt] < x) cnt = 2 * cnt + 1;else cnt = 2 * cnt;tree[cnt] = x;
}void build(char* s, int* tree)
{tree[1] = s[0] - '0';for (int i = 1; s[i]; i++)insert(s[i], tree);
}int main()
{int n;while(~scanf("%d", &n) && n) {scanf("%s", s);memset(tree1, -1, sizeof(tree1));build(s, tree1);while(n--) {scanf("%s", s);memset(tree2, -1, sizeof(tree2));build(s, tree2);bool flag = false;for(int i = 0; i < M; i++)if(tree1[i] != tree2[i]) {flag = true; break;}printf("%s\n", flag ? "NO" : "YES");}}return 0;
}

这篇关于HDU3791 二叉搜索树【二叉搜索树】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---