todo部分正确 天勤 法2 B1043 算法下P318 【重要 综合 树】

//todo部分正确 天勤 法2 1043 Is It a Binary Search Tree 算法下P318 【重要 综合 树】
#include <iostream>
#define maxSize 100
using namespace std;

typedef struct BTNode{
    struct BTNode* LChild;
    struct BTNode* RChild;
    int data;
}BTNode;

int N;
int preorder[maxSize];

void insert1(BTNode* &x,int a){
    if(x == NULL){
        x = new BTNode();
        x->data = a;
        x->LChild = x->RChild = NULL;
    }else{
        if(a < x->data) insert1(x->LChild,a);
        else insert1(x->RChild,a);
    }
}
void insert2(BTNode* &x,int a){
    if(x == NULL){
        x = new BTNode();
        x->data = a;
        x->LChild = x->RChild = NULL;
    }else{
        if(a >= x->data) insert2(x->LChild,a);
        else insert2(x->RChild,a);
    }
}

BTNode* buildTree1(BTNode* root,int index){
    while(index < N) insert1(root,preorder[index++]);
    return root;
}
BTNode* buildTree2(BTNode* root,int index){
    while(index < N) {
        insert2(root,preorder[index]);
        index++;
    }

    return root;
}

int flag1 = 1,M= 0;
void preOrder(BTNode* root){
    if(M<N && root->data != preorder[M]){
        flag1 = 0;
    }
    M++;
    if(root->LChild != NULL) preOrder(root->LChild);
    if(root->RChild != NULL) preOrder(root->RChild);

}

int flag2 = 0;
void postOrder(BTNode* root){
    if(root->LChild != NULL) postOrder(root->LChild);
    if(root->RChild != NULL) postOrder(root->RChild);
    if(flag2 ==0){
        cout<<root->data;
        flag2 = 1;
    }else{
        cout<<" "<<root->data;
    }
}

int main(){
    cin>>N;

    BTNode* root1 = new BTNode();
    root1->LChild = root1->RChild = NULL;
    root1->data = -1;

    BTNode* root2 = new BTNode();
    root2->LChild = root2->RChild = NULL;
    root2->data = -1;

    for(int i=0;i<N;i++){
        cin>>preorder[i];
        if(i==0){
            root1->data = preorder[0];
            root2->data = preorder[0];
        }
    }

    buildTree1(root1,1);
    preOrder(root1);
    if(flag1){
        cout<<"YES"<<endl;
        postOrder(root1);
    }else{
        flag1 = 1,M = 0;
        buildTree2(root2,1);
        preOrder(root2);
        if(flag1){
            cout<<"YES"<<endl;
            postOrder(root2);
        }else cout<<"NO"<<endl;
    }

    return 0;
}