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

这是二叉搜索树吗?

一棵二叉搜索树可被递归地定义为具有下列性质的二叉树:对于任一结点,

  • 其左子树中所有结点的键值小于该结点的键值;
  • 其右子树中所有结点的键值大于等于该结点的键值;
  • 其左右子树都是二叉搜索树。

所谓二叉搜索树的“镜像”,即将所有结点的左右子树对换位置后所得到的树。

给定一个整数键值序列,现请你编写程序,判断这是否是对一棵二叉搜索树或其镜像进行前序遍历的结果。

输入格式:

输入的第一行给出正整数 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<<" ";} }}
}

 

相关文章:

这是二叉搜索树吗?

一棵二叉搜索树可被递归地定义为具有下列性质的二叉树&#xff1a;对于任一结点&#xff0c; 其左子树中所有结点的键值小于该结点的键值&#xff1b;其右子树中所有结点的键值大于等于该结点的键值&#xff1b;其左右子树都是二叉搜索树。 所谓二叉搜索树的“镜像”&#xf…...

5.82 BCC工具之tcpdrop.py解读

一,工具简介 tcpdrop工具打印被内核丢弃的 TCP 数据包或段的详细信息,包括导致丢弃的内核堆栈跟踪。 当网络出现拥堵、资源不足或其他原因导致数据包被内核丢弃时,tcpdrop可以帮助开发者和网络管理员识别并定位问题。 该工具通过钩住内核中处理TCP数据包的相关函数,捕获…...

JavaScript 基础知识

一、初识 JavaScript 1、JS 初体验 JS 有3种书写位置&#xff0c;分别为行内、内部和外部。 示例&#xff1a; <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"wid…...

【判断是否为回文数】

法一&#xff1a;用字符串形式判断&#xff08;依次对比前面和后面的数是否相等&#xff09; #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进一步介绍

个人主页 &#xff1a; zxctscl 如有转载请先通知 文章目录 1. 前言2. 迭代器2.1 反向迭代器2.2 const对象迭代器 3. Capacity3.1 size和length3.2 max_size3.3 capacity3.4 clear3.5 shrink_to_fit &#xff08;了解即可&#xff09;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 项目中&#xff0c;您可以通过 ecosystem.config.js 文件来配置 PM2&#xff0c;以便使用 PM2 来管理 Nuxt.js 应用的进程。ecosystem.config.js 是一个特殊的配置文件&#xff0c;它允许您定义应用的各种属性&#xff0c;如脚本路径、环境变量、日志设置等。 下面…...

个人博客系列-后端项目-用户注册功能(7)

介绍 用户注册API的主要流程&#xff1a;1.前端用户提交用户名&#xff0c;密码 2. 序列化器校验用户名&#xff0c;密码是否合法。3.存入数据库。4.签发token 创建序列化器 from rest_framework import serializers from rest_framework_simplejwt.serializers import Toke…...

vue项目因内存溢出启动报错

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

UI 学习 二 可访问性 模式

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

Spring学习

Maven 的配置文件是一个强约定的XML格式文件&#xff0c;它的文件名一定是pom.xml。 1、POM (Project Object Model) 一个 Java 项目所有的配置都放置在 POM 文件中&#xff0c;大概有如下的行为&#xff1a; 定义项目的类型、名字管理依赖关系定制插件的 1.maven坐标 <…...

鸿蒙开发-UI-动画-组件内转场动画

鸿蒙开发-UI-组件3 鸿蒙开发-UI-气泡/菜单 鸿蒙开发-UI-页面路由 鸿蒙开发-UI-组件导航-Navigation 鸿蒙开发-UI-组件导航-Tabs 鸿蒙开发-UI-图形-图片 鸿蒙开发-UI-图形-绘制几何图形 鸿蒙开发-UI-图形-绘制自定义图形 鸿蒙开发-UI-图形-页面内动画 文章目录 前言 一、基本概…...

Leet code 179 最大数

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

swagger踩坑之请求类不显示具体字段

swagger踩坑之请求类不显示具体字段 省流&#xff1a;枚举字段需要加上ApiModelProperty注解 过程复现&#xff1a; TestEnum 枚举不加注解&#xff0c;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

目录 一、前提卸载命令&#xff1a;执行情况&#xff1a; 二、安装 Docker1. 通过仓库进行安装&#xff08;在线方式&#xff09;1.1 设置存储库1.2 查看可安装版本1.3 安装 Docker1.4 启动 Docker1.5 验证是否成功 2. 通过 RMP 包安装&#xff08;离线方式&#xff09;2.2 安装…...

Doris部署学习(一)

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

QT下跨平台库实现及移植经验分享

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

8:00面试,8:06就出来了,问的问题有点变态。。。

从小厂出来&#xff0c;没想到在另一家公司又寄了。 到这家公司开始上班&#xff0c;加班是每天必不可少的&#xff0c;看在钱给的比较多的份上&#xff0c;就不太计较了。没想到9月一纸通知&#xff0c;所有人不准加班&#xff0c;加班费不仅没有了&#xff0c;薪资还要降40%…...

RestClient

什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端&#xff0c;它允许HTTP与Elasticsearch 集群通信&#xff0c;而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级&#xff…...

ServerTrust 并非唯一

NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...

CSS设置元素的宽度根据其内容自动调整

width: fit-content 是 CSS 中的一个属性值&#xff0c;用于设置元素的宽度根据其内容自动调整&#xff0c;确保宽度刚好容纳内容而不会超出。 效果对比 默认情况&#xff08;width: auto&#xff09;&#xff1a; 块级元素&#xff08;如 <div>&#xff09;会占满父容器…...

#Uniapp篇:chrome调试unapp适配

chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器&#xff1a;Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...

使用Spring AI和MCP协议构建图片搜索服务

目录 使用Spring AI和MCP协议构建图片搜索服务 引言 技术栈概览 项目架构设计 架构图 服务端开发 1. 创建Spring Boot项目 2. 实现图片搜索工具 3. 配置传输模式 Stdio模式&#xff08;本地调用&#xff09; SSE模式&#xff08;远程调用&#xff09; 4. 注册工具提…...

Linux 中如何提取压缩文件 ?

Linux 是一种流行的开源操作系统&#xff0c;它提供了许多工具来管理、压缩和解压缩文件。压缩文件有助于节省存储空间&#xff0c;使数据传输更快。本指南将向您展示如何在 Linux 中提取不同类型的压缩文件。 1. Unpacking ZIP Files ZIP 文件是非常常见的&#xff0c;要在 …...

二维FDTD算法仿真

二维FDTD算法仿真&#xff0c;并带完全匹配层&#xff0c;输入波形为高斯波、平面波 FDTD_二维/FDTD.zip , 6075 FDTD_二维/FDTD_31.m , 1029 FDTD_二维/FDTD_32.m , 2806 FDTD_二维/FDTD_33.m , 3782 FDTD_二维/FDTD_34.m , 4182 FDTD_二维/FDTD_35.m , 4793...

解析“道作为序位生成器”的核心原理

解析“道作为序位生成器”的核心原理 以下完整展开道函数的零点调控机制&#xff0c;重点解析"道作为序位生成器"的核心原理与实现框架&#xff1a; 一、道函数的零点调控机制 1. 道作为序位生成器 道在认知坐标系$(x_{\text{物}}, y_{\text{意}}, z_{\text{文}}…...

【iOS】 Block再学习

iOS Block再学习 文章目录 iOS Block再学习前言Block的三种类型__ NSGlobalBlock____ NSMallocBlock____ NSStackBlock__小结 Block底层分析Block的结构捕获自由变量捕获全局(静态)变量捕获静态变量__block修饰符forwarding指针 Block的copy时机block作为函数返回值将block赋给…...

【java】【服务器】线程上下文丢失 是指什么

目录 ■前言 ■正文开始 线程上下文的核心组成部分 为什么会出现上下文丢失&#xff1f; 直观示例说明 为什么上下文如此重要&#xff1f; 解决上下文丢失的关键 总结 ■如果我想在servlet中使用线程&#xff0c;代码应该如何实现 推荐方案&#xff1a;使用 ManagedE…...