对于二叉搜索树，我们规定任一结点的左子树仅包含严格小于该结点的键值，而其右子树包含大于或等于该结点的键值。如果我们交换每个节点的左子树和右子树，得到的树叫做镜像二叉搜索树。

现在我们给出一个整数键值序列，请编写程序判断该序列是否为某棵二叉搜索树或某镜像二叉搜索树的前序遍历序列，如果是，则输出对应二叉树的后序遍历序列。

输入格式:

输入的第一行包含一个正整数N（≤1000），第二行包含N个整数，为给出的整数键值序列，数字间以空格分隔。

输出格式:

输出的第一行首先给出判断结果，如果输入的序列是某棵二叉搜索树或某镜像二叉搜索树的前序遍历序列，则输出YES，否侧输出NO。如果判断结果是YES，下一行输出对应二叉树的后序遍历序列。数字间以空格分隔，但行尾不能有多余的空格。

输入样例1:

7
8 6 5 7 10 8 11

输出样例1:

YES
5 7 6 8 11 10 8

输入样例2:

7
8 6 8 5 10 9 11

输出样例2:

NO

 

#include<bits/stdc++.h>
using namespace std;
const int maxn=1005;
typedef struct node* BinTree;
int n,s,t;
int a[maxn],b[maxn],c[maxn];
struct node{
    int data;
    BinTree left,right;
};

BinTree CreatTree(BinTree BST,int x){
    if(!BST){
        BST=(BinTree)malloc(sizeof(struct node));
        BST->data=x;
        BST->left=BST->right=NULL;
    }
    else{
        if(x<BST->data)
            BST->left=CreatTree(BST->left,x);
        else
            BST->right=CreatTree(BST->right,x);
    }
    return BST;
}

void PreorderTraversal(BinTree BST){
    if(BST){
        b[s++]=BST->data;
        PreorderTraversal(BST->left);
        PreorderTraversal(BST->right);
    }
}

void MirrorPreorderTraversal(BinTree BST){
    if(BST){
        c[t++]=BST->data;
        MirrorPreorderTraversal(BST->right);
        MirrorPreorderTraversal(BST->left);
    }
}

int k1;
void PostorderTraversal(BinTree BST){
    if(BST){
        PostorderTraversal(BST->left);
        PostorderTraversal(BST->right);
        if(k1) cout<<" ";
        cout<<BST->data;
        k1=1;
    }
}

int k2;
void MirrorPostorderTraversal(BinTree BST){
    if(BST){
        MirrorPostorderTraversal(BST->right);
        MirrorPostorderTraversal(BST->left);
        if(k2) cout<<" ";
        cout<<BST->data;
        k2=1;
    }
}

int main(){
    BinTree BST;
    BST=NULL;
    cin>>n;
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
        BST=CreatTree(BST,a[i]);
    }
    PreorderTraversal(BST);
    MirrorPreorderTraversal(BST);
    int flag1=1,flag2=1;
    for(int i=0;i<n;i++){
        if(a[i]!=b[i]) flag1=0;
        if(a[i]!=c[i]) flag2=0;
        if(!flag1 && !flag2) break;
    }

    if(!flag1&&!flag2)
        cout<<"NO";
    else{
        cout<<"YES"<<endl;
        if(flag1)
            PostorderTraversal(BST);
        else
            MirrorPostorderTraversal(BST);
    }
    return 0;
}

View Code