L2-004 is this a binary search tree? (25 points)

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;
}