要求：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
思路：
后序遍历定义： [ 左子树 | 右子树 | 根节点 ] ，即遍历顺序为 “左、右、根” 。
二叉搜索树定义： 左子树中所有节点的值 < 根节点的值；右子树中所有节点的值 > 根节点的值；其左、右子树也分别为二叉搜索树。
方法一：递归法
发现对于每一棵子树，它的根结点总是对应该子树的后序序列的最后一个数。
那么，只需要不断地确定出左子树区间和右子树区间，并且判断：左子树区间的所有结点值 < 根结点值 < 右子树区间所有结点值，这个条件是否满足即可。
先来一次遍历以确定出左右子树的分界点，然后再分别对两棵子树进行递归判断。现在让我们来分析一下递归方法的时间复杂度：以标准的完美二叉搜索树为例，递归的每一层都涉及到对序列的遍历，虽然层数越深节点越少（少了子树的根节点），但是这种减少是微不足道的，即使是到了最底层，依旧有n/2的节点（完美二叉树第i层节点数是其上所有节点数之和+1），因此递归方法在每一层的遍历开销是O(n)，而对于二叉树而言，递归的层数平均是O(logn)，因此，递归方法的最终复杂度是O(nlogn)
public class L34_VerifySquenceOfBST {
public boolean VerifyPostorder(int[] postorder){
if(postorder==null||postorder.length==0)return false;
return recur(postorder, 0, postorder.length-1);
}
public boolean recur(int[] postorder, int start, int end){
// 递归结束条件
if(start>=end)return true;
// 临时指针p指向序列的起始位
int p = start;
while(postorder[p]<postorder[end])p++; // p遍历到左子树结束，右子树的开始
// 此时退出循环的时候，表明p点指向了右子树的开始，并把位置保存起来到m
int m = p;
while(postorder[p]>postorder[end])p++; // p遍历到右子树结束
// 如果postorder是二叉搜索树，那么p点会顺利到达末尾，因为它满足前面的条件
return p==end && recur(postorder,start,m-1)&&recur(postorder,m,end-1);
}
}
方法二：设置辅助栈
翻转先序遍历又是root->right->left的，基于这样的性质和遍历方式，我们知道越往右越大，这样，就可以构造一个单调递增的栈，来记录遍历的元素。
为什么要用单调栈呢，因为往右子树遍历的过程，value是越来越大的，一旦出现了value小于栈顶元素value的时候，就表示要开始进入左子树了
单调栈帮我们记录了这些节点，只要栈顶元素还比当前节点大，就表示还是右子树，要移除，因为我们要找到这个左孩子节点直接连接的父节点，也就是找到这个子树的根，只要栈顶元素还大于当前节点，就要一直弹出，直到栈顶元素小于节点，或者栈为空。栈顶的上一个元素就是子树节点的根。
接下来，数组继续往前遍历，之后的左子树的每个节点，都要比子树的根要小，才能满足二叉搜索树，否则就不是二叉搜索树。
// 方法二：设定辅助栈
public boolean VerifyPostorder2(int[] postorder){
// 借助一个单调栈 stack存储值递增的节点；
Stack<Integer> stack = new Stack<>();
// 倒序，从尾部开始
int index = postorder.length-1;
// 将根节点设置为整型的最大值,表示上一个根节点的元素
int root = Integer.MAX_VALUE;
while(index>=0){
// 左子树元素必须要小于递增栈被peek访问的元素，否则就不是二叉搜索树
if(postorder[index]>root)return false;
// 每当遇到值递减的节点ri,则通过出栈来更新节点ri的父节点 root
while(!stack.isEmpty()&&postorder[index]<stack.peek()){
// 数组元素小于单调栈的元素了，表示往左子树走了，记录下上个根节点
// 找到这个左子树对应的根节点，之前右子树全部弹出，不再记录，因为不可能在往根节点的右子树走了
root=stack.pop();
}
stack.add(postorder[index--]);
}
return true;
}
