# Pat l2-004 is this a binary search tree?

#### Title Meaning

Give you an integer n, then an integer n, now let you judge whether the given number is the sequence of a binary search tree or its image.

#### Solving problems

According to the properties of binary search tree, binary tree can be divided into left and right parts by root, otherwise it is not a standard sequence.
In fact, the image binary tree is the left small right big reverse judgment.

#### Code part

```#include <iostream>
#include <stdio.h>
#include <string.h>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn=1100;
bool vis;
int pre[maxn];
vector <int> be;
void f(int left,int right)
{
if(left>right)
return;
int tl=left+1;
int tr=right;
if(!vis)
{
while(tl<=right&&pre[tl]<pre[left])
tl++;
while(tr>left&&pre[tr]>=pre[left])
tr--;
}
else
{
while(tl<=right&&pre[tl]>=pre[left])
tl++;
while(tr>left&&pre[tr]<pre[left])
tr--;
}
if(tl-tr!=1)
return;
f(left+1,tr);
f(tl,right);
be.push_back(pre[left]);
}
int main()
{
int n;
while(~scanf("%d",&n))
{
for(int i=0; i<n; ++i)
{
scanf("%d",&pre[i]);
}
f(0,n-1);
if(be.size()!=n)
{
vis=1;
be.clear();
f(0,n-1);
}
if(be.size()!=n)
{
printf("NO\n");

}
else
{
printf("YES\n%d",be);
for(int i=1; i<n; ++i)
printf(" %d",be[i]);
printf("\n");
}
}
return 0;
}```

Added by Brendan Nolan on Sun, 05 Apr 2020 12:17:06 +0300