这是二叉搜索树吗?
一棵二叉搜索树可被递归地定义为具有下列性质的二叉树:对于任一结点,
- 其左子树中所有结点的键值小于该结点的键值;
- 其右子树中所有结点的键值大于等于该结点的键值;
- 其左右子树都是二叉搜索树。
所谓二叉搜索树的“镜像”,即将所有结点的左右子树对换位置后所得到的树。
给定一个整数键值序列,现请你编写程序,判断这是否是对一棵二叉搜索树或其镜像进行前序遍历的结果。
输入格式:
输入的第一行给出正整数 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<bits/stdc++.h>
using namespace std;
struct Node{int data;Node *l;Node *r;
};
vector<int>s,pre1,pre2,post1,post2;//先构造树
Node *build(Node *root,int x){if(root==NULL){root = new Node;root->l = root->r = NULL;root->data = x;}else if(x<root->data){ //小于根节点说明是左子树 root->l = build(root->l,x);}else{ //大于根节点说明是右子树 root->r = build(root->r,x);}return root;
} void preorder1(Node *root){ //前序遍历(根左右) if(root==NULL){return;}pre1.push_back(root->data);preorder1(root->l);preorder1(root->r);
}
void preorder2(Node *root){ //前序遍历的逆遍历(根右左) if(root==NULL){return;}pre2.push_back(root->data);preorder2(root->r);preorder2(root->l);
}
void postorder1(Node *root){ //后序遍历(左右根) if(root==NULL){return;}postorder1(root->l);postorder1(root->r);post1.push_back(root->data);
}
void postorder2(Node *root){ //后序遍历的逆遍历(右左根) if(root==NULL){return;}postorder2(root->r);postorder2(root->l);post2.push_back(root->data);
}
int main(){int n;cin>>n;Node *root = NULL;for(int i = 0;i<n;i++){int t;cin>>t;root = build(root,t);s.push_back(t);}preorder1(root); //进行前序遍历 if(s!=pre1){ //如果不是前序遍历就进行前序遍历的逆遍历 preorder2(root);if(s!=pre2){ //如果也不是前序遍历的逆遍历就输出NO cout<<"NO";}else{ //如果是前序遍历的逆遍历就输出YES cout<<"YES"<<endl;postorder2(root); //进行后序遍历的逆遍历然后输出 for(int i = 0;i<n;i++){cout<<post2[i];if(i!=n-1){cout<<" ";}}}}else{ //如果是前序遍历就输出YES cout<<"YES"<<endl;postorder1(root); //进行后序遍历然后输出 for(int i = 0;i<n;i++){cout<<post1[i];if(i!=n-1){cout<<" ";} }}
}
相关文章:
这是二叉搜索树吗?
一棵二叉搜索树可被递归地定义为具有下列性质的二叉树:对于任一结点, 其左子树中所有结点的键值小于该结点的键值;其右子树中所有结点的键值大于等于该结点的键值;其左右子树都是二叉搜索树。 所谓二叉搜索树的“镜像”…...
5.82 BCC工具之tcpdrop.py解读
一,工具简介 tcpdrop工具打印被内核丢弃的 TCP 数据包或段的详细信息,包括导致丢弃的内核堆栈跟踪。 当网络出现拥堵、资源不足或其他原因导致数据包被内核丢弃时,tcpdrop可以帮助开发者和网络管理员识别并定位问题。 该工具通过钩住内核中处理TCP数据包的相关函数,捕获…...

JavaScript 基础知识
一、初识 JavaScript 1、JS 初体验 JS 有3种书写位置,分别为行内、内部和外部。 示例: <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"wid…...
【判断是否为回文数】
法一:用字符串形式判断(依次对比前面和后面的数是否相等) #include<stdio.h> #include<string.h> int main() {char st[100];scanf("%s",st);int flag1,nstrlen(st);for(int i0,jn-1;i<n,j>0;i,j--){if(st[i]!…...

【C++】string进一步介绍
个人主页 : zxctscl 如有转载请先通知 文章目录 1. 前言2. 迭代器2.1 反向迭代器2.2 const对象迭代器 3. Capacity3.1 size和length3.2 max_size3.3 capacity3.4 clear3.5 shrink_to_fit (了解即可)3.6 reserve3.7 resize 4. Element access4…...
思科设备下面主机访问公网经常时好时坏延迟大丢包不稳定
环境: 思科防火墙ASA5555 Cisco Adaptive Security Appliance Software Version 9.4(2)6 Device Manager Version 7.5(2)153 内外为DMZ区域 思科交换机(C3560E-UNIVERSALK9-M), Version 12.2(55)SE5 主机 centos 7 问题描述: 思科设备下面主机访问公网经常时好时坏不稳定…...
nuxtjs 如何通过ecosystem.config.js配置pm2?
在 Nuxt.js 项目中,您可以通过 ecosystem.config.js 文件来配置 PM2,以便使用 PM2 来管理 Nuxt.js 应用的进程。ecosystem.config.js 是一个特殊的配置文件,它允许您定义应用的各种属性,如脚本路径、环境变量、日志设置等。 下面…...

个人博客系列-后端项目-用户注册功能(7)
介绍 用户注册API的主要流程:1.前端用户提交用户名,密码 2. 序列化器校验用户名,密码是否合法。3.存入数据库。4.签发token 创建序列化器 from rest_framework import serializers from rest_framework_simplejwt.serializers import Toke…...

vue项目因内存溢出启动报错
前端能正常启动,但只要一改动就报错启动出错。 解决办法: 安装依赖 npm install cross-env increase-memory-limit 然后再做两件事:在node 在package.json 里的 script 里进行配置 LIMIT是你想分配的内存大小,这里的8192单位…...

UI 学习 二 可访问性 模式
教程:Accessibility – Material Design 3 一 颜色对比 颜色和对比度可以用来帮助用户看到和理解应用程序的内容,与正确的元素交互,并理解操作。 颜色可以帮助传达情绪、语气和关键信息。可以选择主色、辅助色和强调色来支持可用性。元素之…...

Spring学习
Maven 的配置文件是一个强约定的XML格式文件,它的文件名一定是pom.xml。 1、POM (Project Object Model) 一个 Java 项目所有的配置都放置在 POM 文件中,大概有如下的行为: 定义项目的类型、名字管理依赖关系定制插件的 1.maven坐标 <…...
鸿蒙开发-UI-动画-组件内转场动画
鸿蒙开发-UI-组件3 鸿蒙开发-UI-气泡/菜单 鸿蒙开发-UI-页面路由 鸿蒙开发-UI-组件导航-Navigation 鸿蒙开发-UI-组件导航-Tabs 鸿蒙开发-UI-图形-图片 鸿蒙开发-UI-图形-绘制几何图形 鸿蒙开发-UI-图形-绘制自定义图形 鸿蒙开发-UI-图形-页面内动画 文章目录 前言 一、基本概…...

Leet code 179 最大数
解题思路 贪心算法 贪心算法就是走一步看一步 每一步都取当前位置的最优解 这题我们该如何贪呢? 我们先把int数组转换为string数组 以示例2为例 3 30 34 5 9 排序哪个在前哪个在后? 3 30 (330)> 30 3 (30…...

swagger踩坑之请求类不显示具体字段
swagger踩坑之请求类不显示具体字段 省流:枚举字段需要加上ApiModelProperty注解 过程复现: TestEnum 枚举不加注解,swagger的UI类不显示详细字段 Data Accessors(chain true) ApiModel(value "test对象", description &quo…...

案例分析篇14:信息系统安全设计考点(2024年软考高级系统架构设计师冲刺知识点总结系列文章)
专栏系列文章推荐: 2024高级系统架构设计师备考资料(高频考点&真题&经验)https://blog.csdn.net/seeker1994/category_12593400.html 【历年案例分析真题考点汇总】与【专栏文章案例分析高频考点目录】(2024年软考高级系统架构设计师冲刺知识点总结-案例分析篇-…...

前端之用HTML弄一个古诗词
将进酒 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>将进酒</title><h1><big>将进酒</big> 君不见黄河之水天上来</h1><table><tr><td ><img…...
Linux 安装使用 Docker
目录 一、前提卸载命令:执行情况: 二、安装 Docker1. 通过仓库进行安装(在线方式)1.1 设置存储库1.2 查看可安装版本1.3 安装 Docker1.4 启动 Docker1.5 验证是否成功 2. 通过 RMP 包安装(离线方式)2.2 安装…...

Doris部署学习(一)
目录 前言 一、Docker容器支持 二、Doris编译步骤 1.拉取镜像 2.构建Docker编译容器 3.下载源码并编译 前言 本文档主要介绍如何通过源码在Docker编译 Doris,以及部署。 一、Docker容器支持 Docker教程:Docker & Docker-Compose 安装教程 - 知…...

QT下跨平台库实现及移植经验分享
最近在移植公司一个QT桌面软件到android上,有一些公司自定义的库,用了很多windows的api,移植过程很是曲折,在此有一些感悟分享一下~ 一.自编写跨平台库 1.有时候为了程序给第三方用需要编译一些qt封装库,并可能跨平台…...

8:00面试,8:06就出来了,问的问题有点变态。。。
从小厂出来,没想到在另一家公司又寄了。 到这家公司开始上班,加班是每天必不可少的,看在钱给的比较多的份上,就不太计较了。没想到9月一纸通知,所有人不准加班,加班费不仅没有了,薪资还要降40%…...

使用VSCode开发Django指南
使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架,专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用,其中包含三个使用通用基本模板的页面。在此…...

简易版抽奖活动的设计技术方案
1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...
java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别
UnsatisfiedLinkError 在对接硬件设备中,我们会遇到使用 java 调用 dll文件 的情况,此时大概率出现UnsatisfiedLinkError链接错误,原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用,结果 dll 未实现 JNI 协…...

【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)
可以使用Sqliteviz这个网站免费编写sql语句,它能够让用户直接在浏览器内练习SQL的语法,不需要安装任何软件。 链接如下: sqliteviz 注意: 在转写SQL语法时,关键字之间有一个特定的顺序,这个顺序会影响到…...
python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)
更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...
三体问题详解
从物理学角度,三体问题之所以不稳定,是因为三个天体在万有引力作用下相互作用,形成一个非线性耦合系统。我们可以从牛顿经典力学出发,列出具体的运动方程,并说明为何这个系统本质上是混沌的,无法得到一般解…...
数据库分批入库
今天在工作中,遇到一个问题,就是分批查询的时候,由于批次过大导致出现了一些问题,一下是问题描述和解决方案: 示例: // 假设已有数据列表 dataList 和 PreparedStatement pstmt int batchSize 1000; // …...

SAP学习笔记 - 开发26 - 前端Fiori开发 OData V2 和 V4 的差异 (Deepseek整理)
上一章用到了V2 的概念,其实 Fiori当中还有 V4,咱们这一章来总结一下 V2 和 V4。 SAP学习笔记 - 开发25 - 前端Fiori开发 Remote OData Service(使用远端Odata服务),代理中间件(ui5-middleware-simpleproxy)-CSDN博客…...
安卓基础(aar)
重新设置java21的环境,临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的: MyApp/ ├── app/ …...

排序算法总结(C++)
目录 一、稳定性二、排序算法选择、冒泡、插入排序归并排序随机快速排序堆排序基数排序计数排序 三、总结 一、稳定性 排序算法的稳定性是指:同样大小的样本 **(同样大小的数据)**在排序之后不会改变原始的相对次序。 稳定性对基础类型对象…...