这道题关键在于判断一棵树是不是 BST
现在题目给出了树的先序序列——我们可以知道这棵树的根，然后题目也给出了 BST 的定义——左子树 ＜ 根 ≤ 右子树（BST 镜像则是 左子树 ≥ 根 ＞ 右子树），那么就可以确定左子树、根、右子树，从而确定这棵二叉树。
所以我们可以通过根和根后续结点确定这棵树是 BST 还是 BST 镜像。如果是 BST，那么后面的子树也要全是 BST；否则后面的子树全是 BST 镜像
所以大概的思路就出来了：
/* 伪码 */
int tree[maxn];//保存输入
bool flag = true;//由于判断是否满足 BST 特性需要所有子树都满足才真正满足条件，而遍历涉及递归不太好返回，所以设置个标志位用来判断
void traversal(当前结点 n, 左子树起始下标 base, 右子树结束下标 end) {
/* 死胡同 */
if (base == end) {//叶子结点
n->data = tree[base];
n->left = n->right = NULL;
return;
}
/* 确定左子树与右子树 */
if (tree[base + 1] < n->data) {//左子树比根小
//利用 BST 特性找到 tree[] 中第一个大于等于根的就是左右子树分界
} else {
//同理
}
if (l - 1 != r) flag = false;//如果这个分界不是相差 1, 那就不满足
/* 递归式 */
traversal(n->left, base, 分界线 - 1);
traversal(n->right, 分界线, end);
} 遗憾的是，最后程序 PA。我在 debug 时发现了一例逻辑错误的例子，留着后面再回顾了：
/*
暂时发现了一个逻辑错误的例子：
5
2 4 3 5 1
无论是 BST 还是 BST 镜像最后输出应该是 "NO" 而目前程序输出 "YES"
错误原因是：
（如果按 BST 来组织）既然 [1] 比 [0] 大，那么 [1] 后面的结点应该全是右子树————全比 [0] 大；
（如果按 BST 镜像来组织）既然 [1] 比 [0] 大，那么 [1]~[3] 应该是左子树————但这棵左子树又不满足 BST 特性
修改了很久都没改出来，所以先放着 :-(
*/ 点击获取完整代码