一棵二叉搜索树可被递归地定义为具有下列性质的二叉树：对于任一结点，
- 其左子树中所有结点的键值小于该结点的键值；
- 其右子树中所有结点的键值大于等于该结点的键值；
- 其左右子树都是二叉搜索树。
所谓二叉搜索树的“镜像”，即将所有结点的左右子树对换位置后所得到的树。
给定一个整数键值序列，现请你编写程序，判断这是否是对一棵二叉搜索树或其镜像进行前序遍历的结果。
输入格式：
输入的第一行给出正整数 N（≤1000）。随后一行给出 N 个整数键值，其间以空格分隔。
输出格式：
如果输入序列是对一棵二叉搜索树或其镜像进行前序遍历的结果，则首先在一行中输出 YES ，然后在下一行输出该树后序遍历的结果。数字间有 1 个空格，一行的首尾不得有多余空格。若答案是否，则输出 NO。
输入样例 1：
1. 7 2. 8 6 5 7 10 8 11
结尾无空行
输出样例 1：
1. YES 2. 5 7 6 8 11 10 8
结尾无空行
输入样例 2：
1. 7 2. 8 10 11 8 6 7 5
结尾无空行
输出样例 2：
1. YES 2. 11 8 10 7 5 6 8
结尾无空行
输入样例 3：
1. 7 2. 8 6 8 5 10 9 11
结尾无空行
输出样例 3：
NO
结尾无空行
思路：如果一颗二叉树的前序是符合规则的，那么他一定有一个与之对应的后序序列 ，按照题意模拟一下就行了
#include<iostream> #include<vector> using namespace std; const int N=1010; int a[N],n,t; vector<int>post; void get_post(int l,int r) { int i=l+1,j=r; if(l>r) return ; if(!t)//反转前 { while(i<=r&&a[i]<a[l]) i++; while(j>l&&a[j]>=a[l]) j--; } else//反转后 { while(i<=r&&a[i]>=a[l]) i++; while(j>l&&a[j]<a[l]) j--; } if(i-j!=1) return ; get_post(l+1,j); get_post(i,r); post.push_back(a[l]);//后序 } int main() { cin>>n; for(int i=0;i<n;i++) cin>>a[i]; get_post(0,n-1); if(post.size()!=n)//后序是否存在 { t=1;//标记，令左右子树反转 post.clear();//清空 get_post(0,n-1); } if(post.size()==n)//满足 { cout<<"YES\n"; for(int i=0;i<post.size();i++) { if(i) cout<<' '; cout<<post[i]; } } else cout<<"NO\n"; return 0; }
