题目链接：点击打开链接
题目大意：给定一个整数键值序列，现请你编写程序，判断这是否是对一棵二叉搜索树或其镜像进行前序遍历的结果。
解题思路：假设它是二叉搜索树，一开始isMirror为FALSE，根据二叉搜索树的性质将已知的前序转换为后序，转换过程中，如果发现最后输出的后序数组长度不为n，那就设isMirror为true，然后清空后序数组，重新再转换一次（根据镜面二叉搜索树的性质），如果依旧转换后数组大小不等于n，就输出no否则输出yes。
AC 代码
#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a); #define INF 0x3f3f3f3f #define MOD 1000000007 using namespace std; typedef long long ll; vector<int> pre,post; int isMirror; // default 0 void getPost(int rt, int tail) { if(rt>tail) return; int i=rt+1, j=tail; if(!isMirror) { while(i<=tail && pre[rt]>pre[i]) i++; while(j>rt && pre[rt]<=pre[j]) j--; } else { while(i<=tail && pre[rt]<=pre[i]) i++; while(j>rt && pre[rt]>pre[j]) j--; } if(i-j!=1) return; getPost(rt+1,j); getPost(i,tail); post.push_back(pre[rt]); } int main() { int n,a; while(~scanf("%d",&n)) { isMirror=0; pre.clear(); post.clear(); for(int i=0;i<n;i++) { scanf("%d",&a); pre.push_back(a); } getPost(0,n-1); if(post.size()!=n) { isMirror=1; post.clear(); getPost(0,n-1); } if(post.size()==n) { printf("YES\n%d",post[0]); for(int i=1;i<n;i++) printf(" %d",post[i]); puts(""); } else puts("NO"); } return 0; }
