HDU 3791 二叉搜索树

拼搏现实的明天。 2024-02-17 21:19 12阅读 0赞

## 二叉搜索树 ##

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

分析：二叉搜索树求解，用数组存储节点，然后两数组相比就行了，由于树的深度最大为10，故数组大小设置为 （2^10）

AC代码：

#include<cstdio>
    #include<cstring>
    #include<cstdlib>
    using namespace std;
    const int maxn=1<<12;
    int a[maxn];
    int b[maxn];
    
    void insert(int* t,char c,int deep){
    	int c1=c-'0';
       if(t[deep]==-1){
       	t[deep]=c1;
       }
       else if(c1<t[deep]){
       	insert(t,c,deep<<1);
       }
       else insert(t,c,deep<<1|1);
    }
    
    
    int main(){
    	int T;
    	while(scanf("%d",&T)==1 &&T){ 
    		memset(a,-1,sizeof(a));
    		char s[12];
    		scanf("%s",s);
    		for(int i=0;i<strlen(s);i++){
    			insert(a,s[i],1);
    		}
    		
           while(T--){
    		memset(b,-1,sizeof(b));
           	scanf("%s",s);
    		for(int i=0;i<strlen(s);i++){
    			insert(b,s[i],1);
    		}
    		
    		int i;
    		for(i=0;i<=(1<<10);i++)
    		{
    			if(a[i]!=b[i])break;
    		}
    		
    		if(i>(1<<10))printf("YES\n");
    		else printf("NO\n");
    	   }
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，12人围观）

还没有评论，来说两句吧...

相关阅读

相关 HDU 3791 二叉搜索树

二叉搜索树 Problem Description 判断两序列是否为同一二叉搜索树序列 Input 开始一个数n，(1<=n<=20) 表示有n

拼搏现实的明天。/ 2024年02月17日 21:19/ 0 赞/ 13 阅读

相关 HDU 3791 二叉搜索树 (基础题)

include<cstdio> include<cstring> using namespace std; const int maxn=102

本是古典何须时尚/ 2024年02月17日 19:05/ 0 赞/ 59 阅读

相关二叉搜索树、平衡二叉树

一、二叉搜索树这里我们不用太多书面化的语言来定义，笔者认为在讨论数据结构、算法相关的内容时用太多书面化、学术化的语言是一种让人很烦的事情。咬文嚼字，不便于读者理解。

阳光穿透心脏的1/2处/ 2023年10月18日 22:26/ 0 赞/ 77 阅读

相关二叉搜索树

搜索树数据结构支持许多动态集合操作，包括SEARCH、MINIMUM、MAXIMUM、PREDECESSOR、SUCCESSOR、INSERT和DELETE等。因此，我们使用一

╰+哭是因爲堅強的太久メ/ 2022年08月14日 01:50/ 0 赞/ 234 阅读

相关 HDOJ-3791（二叉搜索树）

二叉搜索树 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others

青旅半醒/ 2022年08月10日 10:52/ 0 赞/ 119 阅读

相关二叉搜索树

二叉搜索树的特征定义就是：一个节点的左子节点的关键字值小于这个节点，右子节点的关键字大于或等于这个父节点 package Trees; import java.ut

客官°小女子只卖身不卖艺/ 2022年05月31日 00:50/ 0 赞/ 317 阅读

相关二叉搜索树

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RqaDYy

た入场券/ 2022年03月17日 02:18/ 0 赞/ 316 阅读

相关 hdoj 3791 二叉树遍历

二叉搜索树 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others

超、凢脫俗/ 2022年02月04日 06:29/ 0 赞/ 132 阅读

相关二叉搜索树

二叉查找树（Binary Search Tree），或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不

小咪咪/ 2021年12月20日 02:53/ 0 赞/ 337 阅读

相关二叉搜索树

二叉搜索树基本概念二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树: 1. 若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；

妖狐艹你老母/ 2021年11月22日 07:30/ 0 赞/ 388 阅读