L2-004 这是二叉搜索树吗？ (25 分)
一棵二叉搜索树可被递归地定义为具有下列性质的二叉树：对于任一结点，
- 其左子树中所有结点的键值小于该结点的键值；
- 其右子树中所有结点的键值大于等于该结点的键值；
- 其左右子树都是二叉搜索树。
所谓二叉搜索树的“镜像”，即将所有结点的左右子树对换位置后所得到的树。
给定一个整数键值序列，现请你编写程序，判断这是否是对一棵二叉搜索树或其镜像进行前序遍历的结果。
输入格式
输入的第一行给出正整数 \(N\)（\(\leqslant 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
作者：陈越
单位：浙江大学
代码长度限制：16 KB
时间限制：400 ms
内存限制：64 MB
Solution
思路来自柳婼的L2-004. 这是二叉搜索树吗？-PAT团体程序设计天梯赛GPLT
1.二叉搜索树满足 左子树点权 小于 根节点点权，根节点点权 小于等于 右子树点权，且此规则对所有子树适用；
2.前序遍历，即 根+左子树+右子树，后序遍历即为 左子树+右子树+根；
3.则考虑DFS，通过二叉搜索树性质，寻找当前根的左子树部分和右子树部分，直到递归到底层，录入数据便为后序遍历；
4.对于镜像二叉树，规则翻转，重新DFS一遍即可；
std.cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1005;
int n,a[N],ans[N];
bool isMirror;
void dfs(int L,int R){
if(L>R) return;
int i=L+1,j=R;
if(!isMirror){
while(i<=R && a[L]>a[i]) ++i;
while(j>L && a[L]<=a[j]) --j;
} else {
while(i<=R && a[L]<=a[i]) ++i;
while(j>L && a[L]>a[j]) --j;
}
if(i-j!=1) return;
//这里找到的左子树末尾为(i-1)，右子树开始为(j+1);
dfs(L+1,j);
dfs(i,R);
ans[++ans[0]]=a[L];
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
dfs(1,n);
if(ans[0]!=n){
isMirror=1;
ans[0]=0;
dfs(1,n);
}
if(ans[0]==n){
printf("YES\n%d",ans[1]);
for(int i=2;i<=ans[0];++i)
printf(" %d",ans[i]);
} else printf("NO");
return 0;
}