Ladder race -- l2-004 is this a binary search tree? (25 points) (recursive)

L2-004 Is this a binary search tree ？ (25 branch )

A binary search tree can be recursively defined as a binary tree with the following properties ： For any node ,

• The key value of all nodes in the left subtree is less than that of the node ;
• The key value of all nodes in the right subtree is greater than or equal to the key value of the node ;
• Its left and right subtrees are binary search trees .

The so-called binary search tree “ Mirror image ”, That is, the tree obtained by transposing the left and right subtrees of all nodes .

Given a sequence of integer key values , Now please write a program , Judge whether this is the result of preorder traversal of a binary search tree or its image .

Input format ：

The first line of input gives a positive integer  N（≤1000）. The next line shows  N  An integer key value , Separated by spaces .

Output format ：

If the input sequence is the result of preorder traversal of a binary search tree or its image , First output... On one line  YES , And then output the result of traversing the tree in the next line . Between the numbers 1 A space , There must be no extra spaces at the beginning and end of a line . If the answer is no , The output  NO.

sample input 1：

7
8 6 5 7 10 8 11

sample output 1：

YES
5 7 6 8 11 10 8

sample input 2：

7
8 10 11 8 6 7 5

sample output 2：

YES
11 8 10 7 5 6 8

sample input 3：

7
8 6 8 5 10 9 11

sample output 3：

NO

  about   8 6 5 7 10 8 11     

that   L=1,R=7 （ Because the subscript is from 1 Start ）

get（1,7）

l=2,r=7;

Binary search tree （ Non mirror ） in ：l Finally 5  r  by 4  So continue recursion   get( L+1,r);   get(l,R)  ;  hold a[L] Put in ans Inside

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[1010];
vector<int>ans;
int n;
int f;




void get(int L,int R)
{
    if(L>R)return;// Do not meet the conditions directly return
    int l=L+1,r=R;
    if(f)// Binary search tree 
    {
        while(l <= R && a[l] < a[L]) l++;//l Move to the right to find the first one greater than or equal to a[L] Number of numbers 
        while(r > L && a[r] >= a[L]) r--;//r Find the first move to the left a[L] Number of numbers 
    }
    else// Mirrored binary search tree 
    {
       while(l <= R && a[l] >= a[L]) l++;//l Move to the right to find the first one less than a[L] Number of numbers 
        while(r > L && a[r] < a[L]) r--;
    }
    if(l-r!=1)return;// Unqualified 
    
     
    get(L+1,r);
    get(l,R);
    
    ans.push_back(a[L]);
}



int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    get(1,n);// A binary search tree is the result of preorder traversal 
    
    if(ans.size() != n)
    {
        f = 1;
        ans.clear();
        get(1,n);// The result of preorder traversal of a binary search tree 
    }
    if(ans.size() != n) cout<<"NO"<<endl;
    else
	{
        cout<<"YES"<<endl<<ans[0];
        for(int i=1;i<ans.size();i++)
            cout<<" "<<ans[i];
        
        cout << endl;
    }

    
    return 0;
}