HDU 3791 二叉搜索树题解-白红宇

HDU 3791 二叉搜索树题解

阅读量：6088 次

发布时间：2019-06-20

本文共 1255 字，大约阅读时间需要 4 分钟。

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 

一条浙大考研上机题目。考二叉树构建。

直接使用静态数组过了，由于数据不大。

#include 
     
      #include 
      
       #include 
       
        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;}