当前位置:网站首页>L2-004 is this a binary search tree? (25 points)
L2-004 is this a binary search tree? (25 points)
2022-07-06 11:25:00 【%xiao Q】
The question :
You are required to judge whether this is the result of traversing a binary search tree or its image in the previous order
analysis :
We can first assume that this is the result of traversing the binary search tree or its image in the previous order , Then we'll see if the following conditions are met :
We can define one 2 A pointer to the tl,tr, Sweep from front to back and from back to front ,tl Look back before , Find the first location larger than the root node ( That is, the first node of the right subtree ),tr Look backwards , Find the first location smaller than the root node ( That is, the last point of the right subtree ), So if it meets tl - tr == 1, Then it is the binary tree that meets the requirements of the topic , About this reason , You can simulate it according to the example .
Reference code :
#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;
// Determine whether it conforms to the binary search tree
if(flag)
{
while(tl <= r && a[tl] < a[l]) tl++; // Find the first of the right subtree
while(tr > l && a[tr] >= a[l]) tr--; // Find the last one to be a subtree
}
// Determine whether it conforms to its image
else
{
while(tl <= r && a[tl] >= a[l]) tl++;
while(tr > l && a[tr] < a[l]) tr--;
}
if(tl - tr != 1) return ; // disqualification , return
dfs(l + 1, tr); // Traverse left subtree
dfs(tl, r); // Traversal right subtree
ans.push_back(a[l]); // Save by subsequent traversal
}
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;
}
边栏推荐
- Vs2019 desktop app quick start
- 安全测试涉及的测试对象
- Pytorch基础
- AcWing 1294.樱花 题解
- 连接MySQL数据库出现错误:2059 - authentication plugin ‘caching_sha2_password‘的解决方法
- QT creator specifies dependencies
- QT creator support platform
- 打开浏览器的同时会在主页外同时打开芒果TV,抖音等网站
- What does BSP mean
- Error connecting to MySQL database: 2059 - authentication plugin 'caching_ sha2_ The solution of 'password'
猜你喜欢
Basic use of redis
C语言读取BMP文件
Swagger, Yapi interface management service_ SE
Rhcsa certification exam exercise (configured on the first host)
Machine learning -- census data analysis
[free setup] asp Net online course selection system design and Implementation (source code +lunwen)
QT creator shape
Did you forget to register or load this tag
Software testing and quality learning notes 3 -- white box testing
Django运行报错:Error loading MySQLdb module解决方法
随机推荐
Software testing - interview question sharing
Why can't STM32 download the program
Why can't I use the @test annotation after introducing JUnit
[download app for free]ineukernel OCR image data recognition and acquisition principle and product application
[AGC009D]Uninity
AcWing 179. Factorial decomposition problem solution
保姆级出题教程
牛客Novice月赛40
One click extraction of tables in PDF
Codeforces Round #753 (Div. 3)
Punctual atom stm32f103zet6 download serial port pin
Install mongdb tutorial and redis tutorial under Windows
QT creator shape
快来走进JVM吧
[蓝桥杯2017初赛]包子凑数
一键提取pdf中的表格
AcWing 1294.樱花 题解
数据库高级学习笔记--SQL语句
C语言读取BMP文件
Julia 1.6 1.7 common problem solving