pta l2-4(这是二叉搜索树吗?)
2024-08-21 06:08:31
题目链接:https://pintia.cn/problem-sets/994805046380707840/problems/994805070971912192
题意:给定n以及n个整数,问该序列是否为二叉搜索树的前序遍历或者二叉搜索树镜像的前序遍历,若是,则输出YES,并输出其后序遍历,否则输出NO。
思路:先判断是否为二叉搜索树的前序遍历,令is=false,通过递归和二叉搜索树的性质计算其后序遍历序列,若序列长度等于n,即成立,否则令is=true,再次计算其后序遍历序列,若序列长度为n即成立,否则输出“NO”。
AC代码:
#include<bits/stdc++.h>
using namespace std; int n;
vector<int> pre,post;
bool is; void getpost(int l,int r){
int i=l+,j=r;
if(l>r) return;
if(!is){
while(i<=r&&pre[i]<pre[l]) ++i;
while(j>l&&pre[j]>=pre[l]) --j;
}
else{
while(i<=r&&pre[i]>=pre[l]) ++i;
while(j>l&&pre[j]<pre[l]) --j;
}
if(i-j!=) return;
getpost(l+,j);
getpost(i,r);
post.push_back(pre[l]);
} int main(){
scanf("%d",&n);
pre.resize(n);
for(int i=;i<n;++i)
scanf("%d",&pre[i]);
getpost(,n-);
if(post.size()!=n){
is=true;
post.clear();
getpost(,n-);
}
if(post.size()==n){
printf("YES\n%d",post[]);
for(int i=;i<n;++i)
printf(" %d",post[i]);
printf("\n");
}
else
printf("NO\n");
return ;
}
最新文章
- js获取隐藏元素宽高的方法
- BUILD 2015: Visual Studio对GitHub的支持
- Hadoop 1.0 和 2.0 中的数据处理框架 - MapReduce
- System.Web.HttpRequestValidationException——从客户端检测到危险的Request值
- acdream.Triangles(数学推导)
- 微软官方的一段JavaScript判断.net环境
- Java API —— TreeMap类
- JAVA基础英语单词表(中)
- 执行指定iframe页面的脚本
- json server服务器
- python tcp黏包和struct模块解决方法,大文件传输方法及MD5校验
- Ubuntu18.04下搭建LAMP环境
- springboot 前后端分离项目跨域配置
- CSS高级布局
- SpringMVC Controller 介绍及常用注解
- [5] 柱台(Cylinder)图形的生成算法
- 基于Quartz.net的远程任务管理系统 二
- msgrcv,msgsnd进程通信,消息的发送和接收
- 【Python】端口扫描脚本
- Linux线程同步