题目链接
【题意】给定一个序列，判断是否为二叉搜索树的前序遍历序列 或 其镜像的前序遍历；
【分析】
- 建树及遍历模板题（模板戳这） 该题要两个build函数分别建BST和BST镜像；
- 注意插入的时候，当前节点的值val与x的比较不要写错，x是要插入的值，是要与val进行比较的。一开始我这里就出现了些小问题大于小于写反了；
- 求pre和post数组时，一开始是将cnt做参数传进，每次++然后对数组进行赋值，但这样会有问题，就写两个全局变量cnt1和cnt2；
- 注意每次调用getPre()之前cnt1要初始化！还有T1、T2要初始化为NULL！！
- ///在想会不会BST和BST的镜像都符合题意，但是想想感觉不大可能。嗯~
#include<bits/stdc++.h>
using namespace std;
const int maxn=1005;
int pre[maxn],post[maxn],a[maxn],cnt1=0,cnt2=0;
typedef struct node{int val;struct node *left;struct node *right;
}node,*tree;
void insert1(tree &T,int x)
{if(T==NULL){T=new node;T->val=x;T->left=T->right=NULL;}else if(x<T->val)insert1(T->left,x);else if(x>=T->val)insert1(T->right,x);
}
void insert2(tree &T,int x)
{if(T==NULL){T=new node;T->val=x;T->left=T->right=NULL;}else if(x>=T->val)insert2(T->left,x);else if(x<T->val)insert2(T->right,x);
}
void postT(tree T)
{if(T){postT(T->left);postT(T->right);post[cnt2++]=T->val;}
}
void preT(tree T)
{if(T){pre[cnt1++]=T->val;preT(T->left);preT(T->right);}
}
int main()
{int n,flag1=1,flag2=1;tree t1=NULL,t2=NULL;scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d",&a[i]);insert1(t1,a[i]);insert2(t2,a[i]);}preT(t1);for(int i=0;i<n;i++){if(a[i]!=pre[i]){flag1=0;break;}}if(flag1)postT(t1);else{flag2=1;cnt1=cnt2=0;preT(t2);for(int i=0;i<n;i++){if(a[i]!=pre[i]){flag2=0;break;}}if(flag2)postT(t2);}if(flag1 || flag2){cout<<"YES\n"<<post[0];for(int i=1;i<n;i++)cout<<" "<<post[i];cout<<endl;}else cout<<"NO"<<endl;return 0;}