PTA 数据结构与算法题目集(中文)7-4 是否同一棵二叉搜索树 (25 分) 题解
2023-06-13 09:16:58 时间
PTA 数据结构与算法题目集(中文)7-4 是否同一棵二叉搜索树 (25 分)题解
我的GIS/CS学习笔记:https://github.com/yunwei37/ZJU-CS-GIS-ClassNotes <一个浙江大学本科生的计算机、地理信息科学知识库 > 还有不少数据结构和算法相关的笔记以及pta题解哦x
寒假的时候自己学ds的时候写了一下的东西… 思路大概就是,把输入的数组第一个元素作为子树的根,如果根不同,那么树肯定不相同;若根相同,比第一个元素小的元素就在它的左子树里面,比它大的就在它右子树里面,然后递归判断左右子树是否相同。 实现看起来并不很好…不过也懒得重写了毕竟简单x
题干
给定一个插入序列就可以唯一确定一棵二叉搜索树。然而,一棵给定的二叉搜索树却可以由多种不同的插入序列得到。例如分别按照序列{2, 1, 3}和{2, 3, 1}插入初始为空的二叉搜索树,都得到一样的结果。于是对于输入的各种插入序列,你需要判断它们是否能生成一样的二叉搜索树。
输入格式:
输入包含若干组测试数据。每组数据的第1行给出两个正整数N (≤10)和L,分别是每个序列插入元素的个数和需要检查的序列个数。第2行给出N个以空格分隔的正整数,作为初始插入序列。最后L行,每行给出N个插入的元素,属于L个需要检查的序列。
简单起见,我们保证每个插入序列都是1到N的一个排列。当读到N为0时,标志输入结束,这组数据不要处理。
输出格式:
对每一组需要检查的序列,如果其生成的二叉搜索树跟对应的初始序列生成的一样,输出“Yes”,否则输出“No”。
输入样例:
4 2 3 1 4 2 3 4 1 2 3 2 4 1 2 1 2 1 1 2 0
输出样例:
Yes No No
#include<stdio.h>
int same(int ori[],int a[],int n);
int main(){
int n,l;
int ori[10],a[10];
int i,j;
scanf("%d %d\n",&n,&l);
while(n){
for(i=0;i<n;i++)
scanf("%d",&ori[i]);
for(j=0;j<l;j++){
for(i=0;i<n;i++)
scanf("%d",&a[i]);
if(same(ori,a,n))
printf("Yes\n");
else
printf("No\n");
}
for(i=0;i<n;i++)
a[i]=0,ori[i]=0;
scanf("%d %d\n",&n,&l);
}
return 0;
}
//使用一个递归算法进行判断: 应该可以改进一下
int same(int ori[],int a[],int n){
int i=0;
int b[10],b1,c[10],c1;
int d[10],d1,e[10],e1;
b1=c1=d1=e1=0;
if(n==0) return 1;
else if(ori[0]!=a[0]) return 0;
else if(n==1) return 1;
else{
for(i=0;i<n;i++){
if(ori[i]>ori[0])
b[b1++]=ori[i];
else if(ori[i]<ori[0])
c[c1++]=ori[i];
}
for(i=0;i<n;i++){
if(a[i]>a[0])
d[d1++]=a[i];
else if(a[i]<a[0])
e[e1++]=a[i];
}
if(d1!=b1||c1!=e1) return 0;
return same(b,d,b1)&&same(c,e,c1);
}
}
相关文章
- pycharm不能输入中文怎么办_电脑无法转换中文输入法
- python json 编码_python乱码转中文
- Qt: 中文-常量中有换行符[通俗易懂]
- WordPress 中文分词搜索
- 【Java AWT 图形界面编程】Container 容器 ② ( Frame 窗口示例 | Panel 示例 | 窗口中文乱码处理 )
- 如何在Linux系统中安装中文界面(linux怎么换成中文)
- MySQL中文查询解决方案(mysql中文无法查询)
- Linux中如何使用中文命令行(linux中文命令行)
- MySQL模糊查询中文LIKE操作技巧(mysql中文like)
- 智能搜索:Oracle 中文模糊查询实践(oracle中文模糊查询)
- mssql中文编码转换技术实践(mssql 编码转中文)
- MySQL: 让你用中文实现查询精确搜索(mysql以中文查询)
- Oracle中文全文索引高效搜索祕笈(oracle中文全文索引)
- 25字中文文章标题使用oracle10jar加强Java应用程序的数据库连接能力(oracle10.jar)
- Jquery截取中文字符串的实现代码
- PHP实现通过中文字符比率来判断垃圾评论的方法