题目：

二叉搜索树 (BST) 递归定义为具有以下属性的二叉树：

若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值
若它的右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值
它的左、右子树也分别为二叉搜索树

我们将二叉搜索树镜面翻转得到的树称为二叉搜索树的镜像。

现在，给定一个整数序列，请你判断它是否可能是某个二叉搜索树或其镜像进行前序遍历的结果。

思路：知道前序遍历，根据他给出性质可以发现排序后就是中序遍历，通过前序和中序构造出树

代码：

#include<bits/stdc++.h>
using namespace std;


int inorder[1005],postorder[1005],preorder[1005];
int cnt;
bool build(int il,int ir,int pl,int pr,int type)
{
    if(il>ir) return true;
    int k;
    int root=preorder[pl];
    if(!type)
    {
        for(k=il;k<=ir;k++)
            if(inorder[k]==root)
                break;
            if(k>ir) return false;
    }
    else
    {
        for(k=ir;k>=il;k--)
            if(inorder[k]==root)
            break;
        if(k<il) return false;
    }
    bool res=true;
    if(!build(il,k-1,pl+1,pl+1+(k-1-il),type)) res=false;
    if(!build(k+1,ir,pl+1+(k-1-il)+1,pr,type)) res=false;

    postorder[cnt++]=root;
    return res;
}
int main()
{
    int n;
   cin>>n;
   for(int i=0;i<n;i++)
   {
       cin>>preorder[i];
       inorder[i]=preorder[i];
   }
   sort(inorder,inorder+n);

   if(build(0,n-1,0,n-1,0))
   {
       puts("YES");
       cout<<postorder[0];
       for(int i=1;i<n;i++) cout<<' '<<postorder[i];
       cout<<endl;
   }
   else
   {
       reverse(inorder,inorder+n);
       cnt=0;
       if(build(0,n-1,0,n-1,1))
       {
           puts("YES");
           cout<<postorder[0];
           for(int i=1;i<n;i++) cout<<' '<<postorder[i];
           cout<<endl;
       }
       else
        puts("NO");

   }









    return 0;
}