【GPLT 二阶题目集】L2-004 这是二叉搜索树吗?
参考文章:L2-004. 这是二叉搜索树吗?-PAT团体程序设计天梯赛GPLT 作者:柳婼(非常感谢!!!)
一棵二叉搜索树可被递归地定义为具有下列性质的二叉树:对于任一结点,
其左子树中所有结点的键值小于该结点的键值;
其右子树中所有结点的键值大于等于该结点的键值;
其左右子树都是二叉搜索树。
所谓二叉搜索树的“镜像”,即将所有结点的左右子树对换位置后所得到的树。给定一个整数键值序列,现请你编写程序,判断这是否是对一棵二叉搜索树或其镜像进行前序遍历的结果。
输入格式:
输入的第一行给出正整数 N(≤1000)。随后一行给出 N 个整数键值,其间以空格分隔。
输出格式:
如果输入序列是对一棵二叉搜索树或其镜像进行前序遍历的结果,则首先在一行中输出 YES ,然后在下一行输出该树后序遍历的结果。数字间有 1 个空格,一行的首尾不得有多余空格。若答案是否,则输出 NO。
输入样例1:
7
8 6 5 7 10 8 11输出样例1:
YES
5 7 6 8 11 10 8输入样例2:
7
8 10 11 8 6 7 5输出样例2:
YES
11 8 10 7 5 6 8输入样例3:
7
8 6 8 5 10 9 11输出样例3:
NO

#include <iostream>
#include <vector>
using namespace std;vector<int> preOrder; //前序遍历序列
vector<int> postOrder; //后序遍历序列
int n;
bool mirror = false; //是否镜像搜索void creatBiTree(int pl, int pr) //搜索树建立
{if (pl > pr) return;else if (pl == pr) {postOrder.push_back(preOrder[pl]);return;}int l = pl + 1, r = pr;if (!mirror){while (l <= pr && preOrder[l] < preOrder[pl])l++;while (r > pl && preOrder[r] >= preOrder[pl])r--;}else{while (l <= pr && preOrder[l] >= preOrder[pl])l++;while (r > pl && preOrder[r] < preOrder[pl])r--;}if (l - r != 1) return;creatBiTree(pl + 1, r);creatBiTree(l, pr);postOrder.push_back(preOrder[pl]);return;
}int main()
{int temp; cin >> n;for (int i = 0; i < n; i++) {cin >> temp;preOrder.push_back(temp);}creatBiTree(0, n - 1);if (postOrder.size() != n){mirror = true;postOrder.clear();creatBiTree(0, n - 1);}if (postOrder.size() == n){cout << "YES" << endl << postOrder[0];for (int i = 1; i < n; i++)cout << " " << postOrder[i];cout << endl;}elsecout << "NO" << endl;return 0;
}
注意事项:
不知道为什么下面的代码有两个测试点一直过不去……
#include <iostream> #include <vector> #include <stdlib.h> using namespace std;vector<int> preOrder; int n, counts = 0; bool res1 = true, res2 = true;typedef struct biTreeNode { //定义二叉树结点int key;biTreeNode* lchild;biTreeNode* rchild; }biTree, * BiTree;void creatBiTree1(BiTree &T,int pl,int pr) //正常搜索树建立 {if (pl <= pr && res1 == true) {T = (BiTree)malloc(sizeof(biTreeNode));int ll = pl + 1, rl = pl + 1 , lr = pr, rr = pr;T->key = preOrder[pl];for (int i = pl + 1; i <= pr; i++) {if (preOrder[i] < T->key) {ll = i; break; //找到第一个比key小的键值}else if (i == pr) {T->lchild = NULL;}}for (int i = pl + 1; i <= pr; i++) {if (preOrder[i] >= T->key) {lr = i - 1, rl = i;break; //找到第一个比key大或相等的键值}else if (i == pr) {T->rchild = NULL;}}for (int i = rl; i <= rr; i++) {if (preOrder[i] < T->key) {res1 = false; break; //判断右子树序列中是否有非法值}}creatBiTree1(T->lchild, ll, lr);creatBiTree1(T->rchild, rl, rr);}else T = NULL; return; }void creatBiTree2(BiTree& T, int pl, int pr) //镜像搜索树建立 {if (pl <= pr && res2 == true) {T = (BiTree)malloc(sizeof(biTreeNode));int ll = pl + 1, rl = pl + 1, lr = pr, rr = pr;T->key = preOrder[pl];for (int i = pl + 1; i <= pr; i++) {if (preOrder[i] >= T->key) {ll = i;break; //找到第一个比key大或相等的键值}else if (i == pr) {T->lchild = NULL;}}for (int i = pl + 1; i <= pr; i++) {if (preOrder[i] < T->key) {lr = i - 1, rl = i;break; //找到第一个比key小的键值}else if (i == pr) {T->rchild = NULL;}}for (int i = rl; i <= rr; i++) {if (preOrder[i] >= T->key) {res2 = false; break; //判断右子树序列中是否有非法值}}creatBiTree2(T->lchild, ll, lr);creatBiTree2(T->rchild, rl, rr);}else T = NULL;return; }void postPrint(BiTree T) {if (T) {postPrint(T->lchild);postPrint(T->rchild);cout << T->key; counts++;if (counts < n) cout << " ";else cout << endl;}else return; }int main() {int temp; cin >> n;for (int i = 0; i < n; i++) {cin >> temp; preOrder.push_back(temp);}BiTree head1, head2;creatBiTree1(head1, 0, n - 1);creatBiTree2(head2, 0, n - 1);if (res1) {cout << "YES" << endl;postPrint(head1);}else if (res2) {cout << "YES" << endl;postPrint(head2);}else cout << "NO" << endl;return 0; }二阶题完结撒花!!!
如有问题,欢迎提出。
相关文章:
【GPLT 二阶题目集】L2-004 这是二叉搜索树吗?
参考文章:L2-004. 这是二叉搜索树吗?-PAT团体程序设计天梯赛GPLT 作者:柳婼(非常感谢!!!) 一棵二叉搜索树可被递归地定义为具有下列性质的二叉树:对于任一结点, 其左子树中所有结点的键值小于…...
Python Numpy基础教程
本文是一个关于Python numpy的基础学习教程,其中,Python版本为Python 3.x 什么是Numpy Numpy Numerical Python,它是Python中科学计算的核心库,可以高效的处理多维数组的计算。并且,因为它的许多底层函数是用C语言编…...
常见HTTP请求错误码大全
响应码由三位十进制数字组成,它们出现在由HTTP服务器发送的响应的第一行。 响应码分五种类型,由它们的第一位数字表示: 1xx:信息,请求收到,继续处理 2xx:成功,行为被成功地接受、…...
重保期间如何「快速」构建内容安全治理体系?
国际会议、国家会议、大型活动、节日庆典等重要时期,往往也是国内外各类攻击组织活跃的高峰期,大量政企机构的互联网展示窗口都会成为网络攻击的重要目标。 网络攻击方式不但有常见的SQL注入攻击、DDoS攻击等破坏方式,更有开始向恶意篡改方式…...
用Qt开发的ffmpeg流媒体播放器,支持截图、录像,支持音视频播放,支持本地文件播放、网络流播放
前言 本工程qt用的版本是5.8-32位,ffmpeg用的版本是较新的5.1版本。它支持TCP或UDP方式拉取实时流,实时流我采用的是监控摄像头的RTSP流。音频播放采用的是QAudioOutput,视频经ffmpeg解码并由YUV转RGB后是在QOpenGLWidget下进行渲染显示。本…...
第七节 平台设备驱动
在之前的字符设备程序中驱动程序,我们只要调用open() 函数打开了相应的设备文件,就可以使用read()/write() 函数,通过file_operations 这个文件操作接口来进行硬件的控制。这种驱动开发方式简单直观,但是从软件设计的角度看&#…...
代理模式详解
本文首更于《从零开始手把手教你实现一个简单的RPC框架》 。 1. 代理模式2. 静态代理3. 动态代理 3.1. JDK 动态代理机制 3.1.1. 介绍3.1.2. JDK 动态代理类使用步骤3.1.3. 代码示例 3.2. CGLIB 动态代理机制 3.2.1. 介绍3.2.2. CGLIB 动态代理类使用步骤3.2.3. 代码示例 3.3. …...
根据报告20%的白领在一年内做过副业,你有做副业吗?
现在大部分人收入单一,收入都是来源于本职工作,当没有了工作就没有了收入的来源,而生活压力又很大,各种开支,各种消费。所以很多人想要增加收入来源,增加被动收入,同时通过副业提升自己的价值和…...
第二十三周周报
学习内容: 修改ViTGAN代码 学习时间: 2.3-2.10 学习产出: 现在的效果 可以看到在700k左右fid开始上升,相比vitgan,改的vitgan鉴别器loss有所下降,但是fid没有降下来,最好为23.134…...
2023年Q1业绩增长背后,迪士尼亟待扭转流媒体亏损困局
重新执掌迪士尼后,鲍勃伊格尔交出了一份表现尚可的“答卷”。 图源:迪士尼 美东时间2023年2月8日,迪士尼披露了2023财年Q1财报,营收为235.1亿美元,同比增长8%;持续经营净利润13亿美元,同比增长11%。受此利…...
LKWA靶场通关和源码分析
文章目录一、Blind RCE?二、XSSI三、PHP Object Injection四、PHP Object Injection(cookie)五、PHP Object Injection(Referer)六、PHAR七、SSRF八、Variables总结一、Blind RCE? 源码: <?php include("sidebar.php"); /***…...
logcpp demo
step1:nug下载log4cppstep2:实现demo#include <iostream>#include <log4cpp/Category.hh>#include <log4cpp/Appender.hh>#include <log4cpp/FileAppender.hh>#include <log4cpp/Priority.hh>#include <log4cpp/Patter…...
平价款的血糖血压监测工具,用它养成健康生活习惯,dido F50S Pro上手
之前看有数据显示国内的三高人群越来越年轻,很多人不到三十就有了高血压、高血糖的问题,埋下了不小的健康隐患,加上前阵子的疫情管控放松,人们了解到了新冠病毒对心脏负担的认知,预防慢病被大众提上了日程,…...
算法训练营 day42 动态规划 理论基础 斐波那契数 爬楼梯 使用最小花费爬楼梯
算法训练营 day42 动态规划 理论基础 斐波那契数 爬楼梯 使用最小花费爬楼梯 理论基础 动态规划,英文:Dynamic Programming,简称DP,如果某一问题有很多重叠子问题,使用动态规划是最有效的。 所以动态规划中每一个状…...
MySQL8 创建用户,设置修改密码,授权
MySQL8 创建用户,设置修改密码,授权 MySQL5.7可以 (创建用户,设置密码,授权) 一步到位 👇 GRANT ALL PRIVILEGES ON *.* TO 用户名% IDENTIFIED BY 密码 WITH GRANT OPTION👆这样的语句在MySQL8.0中行不通, 必须 创设和授权 分步执行👇 CR…...
MySQL —— 内置函数
目录 内置函数 一、日期函数 二、字符串函数 三、数学函数 四、其他函数 内置函数 一、日期函数 函数名称描述current_date()获取当前日期current_time()获取当前时间current_timestamp()获取当前时间戳now()获取当前日期时间date(datetime)获取datetime参数的日期部分d…...
Mybatis框架(全部基础知识)
👌 棒棒有言:也许我一直照着别人的方向飞,可是这次,我想要用我的方式飞翔一次!人生,既要淡,又要有味。凡事不必太在意,一切随缘,缘深多聚聚,缘浅随它去。凡事…...
pixhawk2.4.8使用调试记录—APM固件
目录一、硬件准备二、APM固件、MP地面站下载三、地面站配置1 刷固件2 机架选择3 加速度计校准4 指南针校准5 遥控器校准6 飞行模式7 紧急断电&无头模式8 基础参数设置9 电流计校准10 电调校准11 起飞前检查(每一项都非常重要)12 飞行经验四、遇到的问…...
终于进了字节,记录一下我作为一名测试员磕磕碰碰的三个月找工作经历...
我是裸辞后重新找工作的,从去年到今年,前前后后花了大概三个月,大大小小参加了几百场面试。不是我说,作为一名测试员是真的挺难的,不过很庆幸自己最后拿到了字节的offer,今天在这里做一下记录吧,…...
基于PYTHON django四川旅游景点推荐系统
摘 要基于四川旅游景点推荐系统的设计与实现是一个专为四川旅游景点为用户打造的旅游网站。该课题基于网站比较流行的Python 语言系统架构,B/S三层结构模式,通过Maven项目管理工具进行Jar包版本的控制。本系统用户可以发布个人游记,查看景点使用户达到良…...
日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻
在如今就业市场竞争日益激烈的背景下,越来越多的求职者将目光投向了日本及中日双语岗位。但是,一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧?面对生疏的日语交流环境,即便提前恶补了…...
【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15
缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下: struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...
云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地
借阿里云中企出海大会的东风,以**「云启出海,智联未来|打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办,现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...
基于当前项目通过npm包形式暴露公共组件
1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹,并新增内容 3.创建package文件夹...
学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1
每日一言 生活的美好,总是藏在那些你咬牙坚持的日子里。 硬件:OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写,"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...
Ascend NPU上适配Step-Audio模型
1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统,支持多语言对话(如 中文,英文,日语),语音情感(如 开心,悲伤)&#x…...
Android15默认授权浮窗权限
我们经常有那种需求,客户需要定制的apk集成在ROM中,并且默认授予其【显示在其他应用的上层】权限,也就是我们常说的浮窗权限,那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...
JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案
JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停 1. 安全点(Safepoint)阻塞 现象:JVM暂停但无GC日志,日志显示No GCs detected。原因:JVM等待所有线程进入安全点(如…...
蓝桥杯3498 01串的熵
问题描述 对于一个长度为 23333333的 01 串, 如果其信息熵为 11625907.5798, 且 0 出现次数比 1 少, 那么这个 01 串中 0 出现了多少次? #include<iostream> #include<cmath> using namespace std;int n 23333333;int main() {//枚举 0 出现的次数//因…...
招商蛇口 | 执笔CID,启幕低密生活新境
作为中国城市生长的力量,招商蛇口以“美好生活承载者”为使命,深耕全球111座城市,以央企担当匠造时代理想人居。从深圳湾的开拓基因到西安高新CID的战略落子,招商蛇口始终与城市发展同频共振,以建筑诠释对土地与生活的…...
