L2-004 这是二叉搜索树吗？ (25 分)

题意：

要求你判断这是否是一颗二叉搜索树或其镜像按前序遍历的结果

分析：

我们可以先假设这个是二叉搜索树或其镜像按前序遍历的结果，然后在看是否符合下面的条件：
我们可以定义一个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;
}