首页 > 代码库 > HDU 3791 二叉搜索树 题解
HDU 3791 二叉搜索树 题解
Problem Description
推断两序列是否为同一二叉搜索树序列
Input
開始一个数n,(1<=n<=20) 表示有n个须要推断,n= 0 的时候输入结束。
接下去一行是一个序列,序列长度小于10,包括(0~9)的数字,没有反复数字,依据这个序列能够构造出一颗二叉搜索树。
接下去的n行有n个序列,每一个序列格式跟第一个序列一样,请推断这两个序列能否组成同一颗二叉搜索树。
接下去一行是一个序列,序列长度小于10,包括(0~9)的数字,没有反复数字,依据这个序列能够构造出一颗二叉搜索树。
接下去的n行有n个序列,每一个序列格式跟第一个序列一样,请推断这两个序列能否组成同一颗二叉搜索树。
Output
假设序列同样则输出YES,否则输出NO
Sample Input
2 567432 543267 576342 0
Sample Output
YES NO
一条浙大考研上机题目。考二叉树构建。
直接使用静态数组过了,由于数据不大。
#include <stdio.h> #include <iostream> #include <string> using std::string; using std::cin; const int SIZE = (1<<9)+1; char Tree[SIZE]; char secTree[SIZE]; string root, child; void constrctTree(char T[], char a, int node = 0) { if (T[node] == 'b') { T[node] = a; return ; } if (a < T[node]) constrctTree(T, a, node<<1|1); else constrctTree(T, a, (node+1)<<1); } int main() { int n; secTree[1<<9] = '\0'; Tree[1<<9] = '\0'; while (scanf("%d", &n) && n != 0) { for (int i = 0; i < 1<<9; i++) Tree[i] = 'b'; cin>>root; for (int i = 0; i < (int)root.size(); i++) { constrctTree(Tree, root[i]); } for (int i = 0; i < n; i++) { cin>>child; if (root.size() != child.size()) puts("NO"); else { for (int j = 0; j < 1<<9; j++) secTree[j] = 'b'; for (int i = 0; i < (int)child.size(); i++) { constrctTree(secTree, child[i]); } if (strcmp(Tree, secTree) == 0) puts("YES"); else puts("NO"); } } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。