对于二叉搜索树，我们规定任一结点的左子树仅包含严格小于该结点的键值，而其右子树包含大于或等于该结点的键值。如果我们交换每个节点的左子树和右子树，得到的树叫做镜像二叉搜索树。 现在我们给出一个整数键值序列，请编写程序判断该序列是否为某棵二叉搜索树或某镜像二叉搜索树的前序遍历序列，如果是，则输出对应二叉树的后序遍历序列。
输入格式：
输入的第一行包含一个正整数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思路：
先将该序列以左子树严格小于该结点的键值，而其右子树大于或等于该结点的键值进行建树，然后对该树进行先序遍历和镜像先序遍历 （根->右->左），若序列与这两个结果其中之一相同，则YES并输出后序遍历否则为NO。代码：
#include<bits/stdc++.h> #include<iostream> using namespace std; typedef struct BiNode{ int data; struct BiNode *lchild,*rchild; }BiNode,*BiTree; int N,p=0,q=0; int a[1005],b[1005],c[1005]; int CreateTree(BiTree &T,int key){ if(T==NULL){ T=(BiTree)malloc(sizeof(BiNode)); T->data=key; T->lchild=T->rchild=NULL; } else if(key<T->data){ return CreateTree(T->lchild,key); } else if(key>T->data||key==T->data){ return CreateTree(T->rchild,key); } } int Preorder(BiTree T){ if(T){ b[p++]=T->data; Preorder(T->lchild); Preorder(T->rchild); } } int MirrorPreorder(BiTree T){ if(T){ c[q++]=T->data; MirrorPreorder(T->rchild); MirrorPreorder(T->lchild); } } int z=0; int Postorder(BiTree T){ if(T){ Postorder(T->lchild); Postorder(T->rchild); if(z==1) std::cout<<" "; std::cout<<T->data; z=1; } } int z2=0; int MirrorPostorder(BiTree T){ if(T){ MirrorPostorder(T->rchild); MirrorPostorder(T->lchild); if(z2==1) std::cout<<" "; std::cout<<T->data; z2=1; } } int main(){ BiTree T; T=NULL; std::cin>>N; for(int i=0;i<N;i++){ std::cin>>a[i]; CreateTree(T,a[i]); } Preorder(T); MirrorPreorder(T); int flag1=1,flag2=1; for(int i=0;i<N;i++){ if(a[i]!=b[i]){ flag1=0; break; } } for(int i=0;i<N;i++){ if(a[i]!=c[i]){ flag2=0; break; } } if(flag1==0&&flag2==0){ std::cout<<"NO"<<endl; } else if(flag1==1){ std::cout<<"YES"<<endl; Postorder(T); } else if(flag2==1&&flag1==0){ std::cout<<"YES"<<endl; MirrorPostorder(T); } }