当前位置:网站首页>L2-004 这是二叉搜索树吗? (25 分)
L2-004 这是二叉搜索树吗? (25 分)
2022-07-06 09:14:00 【%xiao Q】
题意:
要求你判断这是否是一颗二叉搜索树或其镜像按前序遍历的结果
分析:
我们可以先假设这个是二叉搜索树或其镜像按前序遍历的结果,然后在看是否符合下面的条件:
我们可以定义一个2个指针tl,tr,分别从前往后扫和从后往前的扫,tl从前往后找,找第一个比根节点节点大的位置(即右子树的第一个节点),tr从后往前找,找第一个比根节点小的位置(即右子树最后一个点),所以如果符合tl - tr == 1,那么就是符合题目要求的二叉树,关于这个原因,你们可以按样例来模拟一下。
参考代码:
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <cmath>
#include <queue>
#include <stack>
#include <algorithm>
#include <unordered_map>
#define LL long long
#define rep(i, a, b) for(int i = a; i <= b; i++)
#define reps(i, a, b) for(int i = a; i < b; i++)
#define pre(i, a, b) for(int i = b; i >= a; i--)
using namespace std;
const int N = 1010;
int a[N];
vector<int> ans;
bool flag = true;
void dfs(int l, int r)
{
if(l > r) return ;
int tl = l + 1, tr = r;
// 判断是否符合二叉搜索树
if(flag)
{
while(tl <= r && a[tl] < a[l]) tl++; //找右子树的第一个
while(tr > l && a[tr] >= a[l]) tr--; //找做子树的最后一个
}
// 判断是否符合其镜像
else
{
while(tl <= r && a[tl] >= a[l]) tl++;
while(tr > l && a[tr] < a[l]) tr--;
}
if(tl - tr != 1) return ; //不符合条件,返回
dfs(l + 1, tr); //遍历左子树
dfs(tl, r); //遍历右子树
ans.push_back(a[l]); //按后续遍历来存
}
int main()
{
int n;
cin >> n;
rep(i, 1, n) cin >> a[i];
dfs(1, n);
if(ans.size() != n)
{
flag = false;
ans.clear();
dfs(1, n);
}
if(ans.size() != n) puts("NO");
else
{
puts("YES");
rep(i, 0, n - 1)
{
if(i) cout << " ";
cout << ans[i];
}
cout << endl;
}
return 0;
}
边栏推荐
- [recommended by bloggers] C WinForm regularly sends email (with source code)
- Database advanced learning notes -- SQL statement
- Postman Interface Association
- How to set up voice recognition on the computer with shortcut keys
- 01项目需求分析 (点餐系统)
- Number game
- 机器学习--人口普查数据分析
- Why can't I use the @test annotation after introducing JUnit
- What does usart1 mean
- [ahoi2009]chess Chinese chess - combination number optimization shape pressure DP
猜你喜欢
图像识别问题 — pytesseract.TesseractNotFoundError: tesseract is not installed or it‘s not in your path
Why can't I use the @test annotation after introducing JUnit
Solve the problem of installing failed building wheel for pilot
CSDN blog summary (I) -- a simple first edition implementation
CSDN markdown editor
neo4j安装教程
Redis的基础使用
Summary of numpy installation problems
Did you forget to register or load this tag
Copie maître - esclave MySQL, séparation lecture - écriture
随机推荐
Introduction and use of automatic machine learning framework (flaml, H2O)
【博主推荐】C#MVC列表实现增删改查导入导出曲线功能(附源码)
Swagger、Yapi接口管理服务_SE
Idea import / export settings file
Install mysql5.5 and mysql8.0 under windows at the same time
[recommended by bloggers] asp Net WebService background data API JSON (with source code)
安全测试涉及的测试对象
AcWing 179. Factorial decomposition problem solution
Ansible实战系列二 _ Playbook入门
AcWing 1298.曹冲养猪 题解
Installation and use of MySQL under MySQL 19 Linux
Mysql 其他主机无法连接本地数据库
MySQL other hosts cannot connect to the local database
Windows cannot start the MySQL service (located on the local computer) error 1067 the process terminated unexpectedly
FRP intranet penetration
The virtual machine Ping is connected to the host, and the host Ping is not connected to the virtual machine
基于apache-jena的知识问答
虚拟机Ping通主机,主机Ping不通虚拟机
Armv8-a programming guide MMU (2)
Leetcode 461 Hamming distance