一棵二叉搜索树可被递归地定义为具有下列性质的二叉树：对于任一结点，
其左子树中所有结点的键值小于该结点的键值；其右子树中所有结点的键值大于等于该结点的键值；其左右子树都是二叉搜索树。所谓二叉搜索树的“镜像”，即将所有结点的左右子树对换位置后所得到的树。
给定一个整数键值序列，现请你编写程序，判断这是否是对一棵二叉搜索树或其镜像进行前序遍历的结果。
输入格式：
输入的第一行给出正整数N（<=1000）。随后一行给出N个整数键值，其间以空格分隔。
输出格式：
如果输入序列是对一棵二叉搜索树或其镜像进行前序遍历的结果，则首先在一行中输出“YES”，然后在下一行输出该树后序遍历的结果。数字间有1个空格，一行的首尾不得有多余空格。若答案是否，则输出“NO”。
输入样例1： 7 8 6 5 7 10 8 11 输出样例1： YES 5 7 6 8 11 10 8 输入样例2： 7 8 10 11 8 6 7 5 输出样例2： YES 11 8 10 7 5 6 8 输入样例3： 7 8 6 8 5 10 9 11 输出样例3： NO题目链接：https://www.patest.cn/contests/gplt/L2-004
思路：建立两个搜索树，一个是它本身，另一个是它镜像；然后分别找出它们各自的前序，跟输入的序列对比，如果相同就输出
对应搜索树或镜像搜索树的后序，否则输出NO;
代码：
#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; int k,a[1010],b[1010],n,c[1010]; typedef struct node { int key; struct node *rchild,*lchild; }Node; int creat1(Node *&p,int num)//搜索树建立； { if(p==NULL) { p=(Node *)malloc(sizeof(Node)); p->key=num; p->rchild=p->lchild=NULL; return 1; } else if(num>=p->key) return creat1(p->rchild,num); else return creat1(p->lchild,num); } void creat2(Node *&N,int num)//镜像搜索树建立； { if(N==NULL) { N=(Node *)malloc(sizeof(Node)); N->key=num; N->lchild=N->rchild=NULL; return ; } else if(num>=N->key) creat2(N->lchild,num); else creat2(N->rchild,num); } void PreOrder1(Node *&ll)//搜索树的前序； { if(ll) { b[k++]=ll->key; PreOrder1(ll->lchild); PreOrder1(ll->rchild); } } void PreOrder2(Node *&kk)//镜像搜索树的前序； { if(kk) { c[k++]=kk->key; PreOrder2(kk->lchild); PreOrder2(kk->rchild); } } void LastOrder(Node *&s)//后序输出； { if(s) { LastOrder(s->lchild); LastOrder(s->rchild); k++; printf(k==n?"%d\n":"%d ",s->key); } } int main() { int i; Node *point1; Node *point2; point1=NULL;///不要忘记赋初值； point2=NULL; scanf("%d",&n); for(i=0; i<n; i++) { scanf("%d",&a[i]); creat1(point1,a[i]);//搜索树建立； creat2(point2,a[i]);//镜像搜索树建立； } k=0; PreOrder1(point1);//搜索树的前序； k=0; PreOrder2(point2);//镜像搜索树的前序； int f=0,g=0; for(i=0; i<n; i++)//判断搜索树和他的镜像的前序是否和输入的一致； { if(a[i]!=b[i]) f=1; if(a[i]!=c[i]) g=1; } k=0; if(!f) { printf("YES\n"); LastOrder(point1); } else if(!g) { printf("YES\n"); LastOrder(point2); } else printf("NO\n"); }