当前位置: 首页 > news >正文

【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 这是二叉搜索树吗?

参考文章&#xff1a;L2-004. 这是二叉搜索树吗&#xff1f;-PAT团体程序设计天梯赛GPLT 作者&#xff1a;柳婼&#xff08;非常感谢!!!&#xff09; 一棵二叉搜索树可被递归地定义为具有下列性质的二叉树&#xff1a;对于任一结点&#xff0c; 其左子树中所有结点的键值小于…...

Python Numpy基础教程

本文是一个关于Python numpy的基础学习教程&#xff0c;其中&#xff0c;Python版本为Python 3.x 什么是Numpy Numpy Numerical Python&#xff0c;它是Python中科学计算的核心库&#xff0c;可以高效的处理多维数组的计算。并且&#xff0c;因为它的许多底层函数是用C语言编…...

常见HTTP请求错误码大全

响应码由三位十进制数字组成&#xff0c;它们出现在由HTTP服务器发送的响应的第一行。 响应码分五种类型&#xff0c;由它们的第一位数字表示&#xff1a; 1xx&#xff1a;信息&#xff0c;请求收到&#xff0c;继续处理 2xx&#xff1a;成功&#xff0c;行为被成功地接受、…...

重保期间如何「快速」构建内容安全治理体系?

国际会议、国家会议、大型活动、节日庆典等重要时期&#xff0c;往往也是国内外各类攻击组织活跃的高峰期&#xff0c;大量政企机构的互联网展示窗口都会成为网络攻击的重要目标。 网络攻击方式不但有常见的SQL注入攻击、DDoS攻击等破坏方式&#xff0c;更有开始向恶意篡改方式…...

用Qt开发的ffmpeg流媒体播放器,支持截图、录像,支持音视频播放,支持本地文件播放、网络流播放

前言 本工程qt用的版本是5.8-32位&#xff0c;ffmpeg用的版本是较新的5.1版本。它支持TCP或UDP方式拉取实时流&#xff0c;实时流我采用的是监控摄像头的RTSP流。音频播放采用的是QAudioOutput&#xff0c;视频经ffmpeg解码并由YUV转RGB后是在QOpenGLWidget下进行渲染显示。本…...

第七节 平台设备驱动

在之前的字符设备程序中驱动程序&#xff0c;我们只要调用open() 函数打开了相应的设备文件&#xff0c;就可以使用read()/write() 函数&#xff0c;通过file_operations 这个文件操作接口来进行硬件的控制。这种驱动开发方式简单直观&#xff0c;但是从软件设计的角度看&#…...

代理模式详解

本文首更于《从零开始手把手教你实现一个简单的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%的白领在一年内做过副业,你有做副业吗?

现在大部分人收入单一&#xff0c;收入都是来源于本职工作&#xff0c;当没有了工作就没有了收入的来源&#xff0c;而生活压力又很大&#xff0c;各种开支&#xff0c;各种消费。所以很多人想要增加收入来源&#xff0c;增加被动收入&#xff0c;同时通过副业提升自己的价值和…...

第二十三周周报

学习内容&#xff1a; 修改ViTGAN代码 学习时间&#xff1a; 2.3-2.10 学习产出&#xff1a; 现在的效果 可以看到在700k左右fid开始上升&#xff0c;相比vitgan&#xff0c;改的vitgan鉴别器loss有所下降&#xff0c;但是fid没有降下来&#xff0c;最好为23.134&#xf…...

2023年Q1业绩增长背后,迪士尼亟待扭转流媒体亏损困局

重新执掌迪士尼后&#xff0c;鲍勃伊格尔交出了一份表现尚可的“答卷”。 图源:迪士尼 美东时间2023年2月8日&#xff0c;迪士尼披露了2023财年Q1财报&#xff0c;营收为235.1亿美元&#xff0c;同比增长8%&#xff1b;持续经营净利润13亿美元&#xff0c;同比增长11%。受此利…...

LKWA靶场通关和源码分析

文章目录一、Blind RCE&#xff1f;二、XSSI三、PHP Object Injection四、PHP Object Injection(cookie)五、PHP Object Injection(Referer)六、PHAR七、SSRF八、Variables总结一、Blind RCE&#xff1f; 源码&#xff1a; <?php include("sidebar.php"); /***…...

logcpp demo

step1&#xff1a;nug下载log4cppstep2&#xff1a;实现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上手

之前看有数据显示国内的三高人群越来越年轻&#xff0c;很多人不到三十就有了高血压、高血糖的问题&#xff0c;埋下了不小的健康隐患&#xff0c;加上前阵子的疫情管控放松&#xff0c;人们了解到了新冠病毒对心脏负担的认知&#xff0c;预防慢病被大众提上了日程&#xff0c;…...

算法训练营 day42 动态规划 理论基础 斐波那契数 爬楼梯 使用最小花费爬楼梯

算法训练营 day42 动态规划 理论基础 斐波那契数 爬楼梯 使用最小花费爬楼梯 理论基础 动态规划&#xff0c;英文&#xff1a;Dynamic Programming&#xff0c;简称DP&#xff0c;如果某一问题有很多重叠子问题&#xff0c;使用动态规划是最有效的。 所以动态规划中每一个状…...

MySQL8 创建用户,设置修改密码,授权

MySQL8 创建用户,设置修改密码,授权 MySQL5.7可以 (创建用户,设置密码,授权) 一步到位 &#x1f447; GRANT ALL PRIVILEGES ON *.* TO 用户名% IDENTIFIED BY 密码 WITH GRANT OPTION&#x1f446;这样的语句在MySQL8.0中行不通, 必须 创设和授权 分步执行&#x1f447; CR…...

MySQL —— 内置函数

目录 内置函数 一、日期函数 二、字符串函数 三、数学函数 四、其他函数 内置函数 一、日期函数 函数名称描述current_date()获取当前日期current_time()获取当前时间current_timestamp()获取当前时间戳now()获取当前日期时间date(datetime)获取datetime参数的日期部分d…...

Mybatis框架(全部基础知识)

&#x1f44c; 棒棒有言&#xff1a;也许我一直照着别人的方向飞&#xff0c;可是这次&#xff0c;我想要用我的方式飞翔一次&#xff01;人生&#xff0c;既要淡&#xff0c;又要有味。凡事不必太在意&#xff0c;一切随缘&#xff0c;缘深多聚聚&#xff0c;缘浅随它去。凡事…...

pixhawk2.4.8使用调试记录—APM固件

目录一、硬件准备二、APM固件、MP地面站下载三、地面站配置1 刷固件2 机架选择3 加速度计校准4 指南针校准5 遥控器校准6 飞行模式7 紧急断电&无头模式8 基础参数设置9 电流计校准10 电调校准11 起飞前检查&#xff08;每一项都非常重要&#xff09;12 飞行经验四、遇到的问…...

终于进了字节,记录一下我作为一名测试员磕磕碰碰的三个月找工作经历...

我是裸辞后重新找工作的&#xff0c;从去年到今年&#xff0c;前前后后花了大概三个月&#xff0c;大大小小参加了几百场面试。不是我说&#xff0c;作为一名测试员是真的挺难的&#xff0c;不过很庆幸自己最后拿到了字节的offer&#xff0c;今天在这里做一下记录吧&#xff0c…...

基于PYTHON django四川旅游景点推荐系统

摘 要基于四川旅游景点推荐系统的设计与实现是一个专为四川旅游景点为用户打造的旅游网站。该课题基于网站比较流行的Python 语言系统架构,B/S三层结构模式&#xff0c;通过Maven项目管理工具进行Jar包版本的控制。本系统用户可以发布个人游记&#xff0c;查看景点使用户达到良…...

springboot 百货中心供应链管理系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;百货中心供应链管理系统被用户普遍使用&#xff0c;为方…...

CMake基础:构建流程详解

目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...

Python爬虫(二):爬虫完整流程

爬虫完整流程详解&#xff08;7大核心步骤实战技巧&#xff09; 一、爬虫完整工作流程 以下是爬虫开发的完整流程&#xff0c;我将结合具体技术点和实战经验展开说明&#xff1a; 1. 目标分析与前期准备 网站技术分析&#xff1a; 使用浏览器开发者工具&#xff08;F12&…...

【Linux系统】Linux环境变量:系统配置的隐形指挥官

。# Linux系列 文章目录 前言一、环境变量的概念二、常见的环境变量三、环境变量特点及其相关指令3.1 环境变量的全局性3.2、环境变量的生命周期 四、环境变量的组织方式五、C语言对环境变量的操作5.1 设置环境变量&#xff1a;setenv5.2 删除环境变量:unsetenv5.3 遍历所有环境…...

恶补电源:1.电桥

一、元器件的选择 搜索并选择电桥&#xff0c;再multisim中选择FWB&#xff0c;就有各种型号的电桥: 电桥是用来干嘛的呢&#xff1f; 它是一个由四个二极管搭成的“桥梁”形状的电路&#xff0c;用来把交流电&#xff08;AC&#xff09;变成直流电&#xff08;DC&#xff09;。…...

[USACO23FEB] Bakery S

题目描述 Bessie 开了一家面包店! 在她的面包店里&#xff0c;Bessie 有一个烤箱&#xff0c;可以在 t C t_C tC​ 的时间内生产一块饼干或在 t M t_M tM​ 单位时间内生产一块松糕。 ( 1 ≤ t C , t M ≤ 10 9 ) (1 \le t_C,t_M \le 10^9) (1≤tC​,tM​≤109)。由于空间…...

WEB3全栈开发——面试专业技能点P4数据库

一、mysql2 原生驱动及其连接机制 概念介绍 mysql2 是 Node.js 环境中广泛使用的 MySQL 客户端库&#xff0c;基于 mysql 库改进而来&#xff0c;具有更好的性能、Promise 支持、流式查询、二进制数据处理能力等。 主要特点&#xff1a; 支持 Promise / async-await&#xf…...

文件上传漏洞防御全攻略

要全面防范文件上传漏洞&#xff0c;需构建多层防御体系&#xff0c;结合技术验证、存储隔离与权限控制&#xff1a; &#x1f512; 一、基础防护层 前端校验&#xff08;仅辅助&#xff09; 通过JavaScript限制文件后缀名&#xff08;白名单&#xff09;和大小&#xff0c;提…...

从零手写Java版本的LSM Tree (一):LSM Tree 概述

&#x1f525; 推荐一个高质量的Java LSM Tree开源项目&#xff01; https://github.com/brianxiadong/java-lsm-tree java-lsm-tree 是一个从零实现的Log-Structured Merge Tree&#xff0c;专为高并发写入场景设计。 核心亮点&#xff1a; ⚡ 极致性能&#xff1a;写入速度超…...

GeoServer发布PostgreSQL图层后WFS查询无主键字段

在使用 GeoServer&#xff08;版本 2.22.2&#xff09; 发布 PostgreSQL&#xff08;PostGIS&#xff09;中的表为地图服务时&#xff0c;常常会遇到一个小问题&#xff1a; WFS 查询中&#xff0c;主键字段&#xff08;如 id&#xff09;莫名其妙地消失了&#xff01; 即使你在…...