二叉搜索树

二叉搜索树的中序遍历一定是一个递增序列

#include<bits/stdc++.h>
using namespace std;
int const N=1e3+7;
int n;
int a[N];
struct node{
    int w;
    node *l,*r;
};
node* dfs(int l,int r,int f){
    if(l>r) return NULL;
    int i=0;
    node *rt=new node;
    rt->w =a[l];
    if(f==0){
        for(i=l+1;i<=r;++i){
            if(a[i]>=a[l]) break;
        }
    }
    else {
        for(i=l+1;i<=r;++i){
            if(a[i]<a[l]) break;
        }
    }
    rt->l =dfs(l+1,i-1,f);
    rt->r =dfs(i,r,f);
    return rt;
}
int cnt,b[N];
void dfs2(node *rt){
    if(rt==NULL) return ;
    dfs2(rt->l );
    b[++cnt]=rt->w ;
    dfs2(rt->r );
}
int pan(node *rt,int f){
    cnt=0;
    dfs2(rt);
    if(f==0){
        for(int i=2;i<=cnt;++i){
            if(b[i-1]>b[i]) return 0;
        }
    }
    else{
        for(int i=2;i<=cnt;++i){
            if(b[i-1]<b[i]) return 0;
        }
    }
    return 1;
}
void dfs3(node* rt){
    if(rt==NULL) return ;
    dfs3(rt->l );
    dfs3(rt->r );
    b[++cnt]=rt->w ;
}
int main(){
    cin >> n;
    for(int i=1;i<=n;++i) cin >> a[i];
    node *rt;
    rt=dfs(1,n,0);
    if(pan(rt,0)){
        cout << "YES\n";
        cnt=0;
        dfs3(rt);
        for(int i=1;i<=cnt;++i){
            cout << b[i];
            if(i!=n) cout << " ";
        }
        return 0;
    }
    rt=dfs(1,n,1);
    if(pan(rt,1)){
        cout << "YES\n";
        cnt=0;
        dfs3(rt);
        for(int i=1;i<=cnt;++i){
            cout << b[i];
            if(i!=n) cout << " ";
        }
        return 0;
    }
    cout << "NO";
    return 0;
}