传送门

思路：可以通过递归来解决该问题。由于题目中要求判断给定序列是否是对一棵二叉搜索树或其镜像进行前序遍历的结果，因此可以考虑使用递归的方式，每次判断以当前节点为根节点的子树是否满足二叉搜索树的定义或其镜像的定义。

$\quad$具体来说，可以先将序列的第一个数作为根节点，然后依次遍历序列中的每一个数。对于每个数，如果它小于根节点的值，那么就将它加入左子树；如果它大于等于根节点的值，那么就将它加入右子树。最后，递归判断左子树和右子树是否分别是二叉搜索树或其镜像，如果都满足，则该序列是对一棵二叉搜索树或其镜像进行前序遍历的结果。

$\quad$判断完以后，我如何确定这颗树的形状以及如何输出这颗树呢？
$\quad$具体来说，输出的办法为在第一次前序遍历检查所给序列是否合法的过程中，将其所对应的树给建立出来，这样我们按后续遍历这棵树就可以得到答案了。

$\quad$这里有一个很重要的点：通过上面构造的过程可以发现，实际上我们最后构造出来的树一定是唯一的，也就是给定任意合法的二叉搜索树的前序序列，则其对应的树也是唯一的

AC Code:

#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define ll() to_ullong() 
#define string() to_string()
#define Endl endl
using namespace std;
typedef long long ll;
typedef pair<int,int>PII; 
typedef unsigned long long ull;
const int M=2010;
const int P=13331;
const ll  llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
#define x first
#define y second
int e[N],ne[N],idx,h[N],w[N];
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++; 
}
//前序遍历：根 左  右
//中序遍历：左 根  右
//后续遍历：左 右  根 
bool dfs1(vector<PII>&ans,int col)
{

      if(ans.size()==0)return true;
      vector<PII>L;//左子树
      vector<PII>R;//右子树
      int root=ans[0].y;
      for(auto c:ans)
       if(c.y!=root)(c.x<ans[0].x?L.push_back(c):R.push_back(c));

      if(col)swap(L,R);


      if(L.size())
      {
         add(root,L[0].y);add(L[0].y,root);
      }
      if(R.size())
      {
         add(root,R[0].y);add(R[0].y,root); 
      }
      return (dfs1(L,col)&&dfs1(R,col));
}//前序遍历构造该树 
vector<int>dfs2(vector<int>&ans,int u,int fa,int col,int id)
{
    if(!id)ans.push_back(w[u]);//前序遍历：根左右 中序遍历:左 根 右  后序遍历：左 右 根 
    vector<int>son;
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(j!=fa)
        {
            son.push_back(j); 
        }
    }//实际上遍历的过程是从后往前的

    if(son.size())
    {
        for(auto c:son)
        {
            vector<int>tmp;
            tmp=dfs2(tmp,c,u,col,id);
            for(auto x:tmp)ans.push_back(x);
        }
    }

    if(id)ans.push_back(w[u]);//后序遍历 
    return ans;
}//跑一遍前序来判断该序列是否为合法的前序遍历序列 
void solve()
{
       int n;cin>>n;
       vector<PII>a;
       for(int i=1;i<=n;i++)
       {
           int x;cin>>x;
           w[i]=x;
           a.push_back({x,i});  
       } 
       memset(h,-1,sizeof h); 
       if(dfs1(a,0))
       {
         vector<int>ans;
         ans=dfs2(ans,1,-1,0,0);//得到浅夏煦遍历序列 

      //     for(auto c:ans)cout<<c<<' ';
         bool flag=true;
         for(int i=0;i<ans.size();i++)
          if(ans[i]!=w[i+1])flag=false;

         if(flag)
         {
             cout<<"YES"<<endl;
             ans.clear();
             ans=dfs2(ans,1,-1,0,1);
             for(int i=0;i<ans.size();i++)
              if(i!=ans.size()-1)cout<<ans[i]<<' ';
              else cout<<ans[i];
             return ;   
         }
       }
       memset(h,-1,sizeof h);//清空一下头 
       if(dfs1(a,1))
       {
         bool flag=true;
         vector<int>ans;
         ans=dfs2(ans,1,-1,1,0);
         for(int i=0;i<ans.size();i++)
          if(ans[i]!=w[i+1])flag=false;

         if(flag)
         {
             cout<<"YES"<<endl;
             ans.clear();
             ans=dfs2(ans,1,-1,1,1);
             for(int i=0;i<ans.size();i++)
              if(i!=ans.size()-1)cout<<ans[i]<<' ';
              else cout<<ans[i];
             return ;   
         }
       }
       cout<<"NO";
       return ;
}
int main()
{
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
        #ifndef ONLINE_JUDGE
        freopen("test.in", "r", stdin);
        #endif
        solve();
        return 0;
}