难度：中等
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
参考以下这颗二叉搜索树：
5
/ \
2 6
/ \
1 3
示例 1：
输入: [1,6,3,2,5]
输出: false
解答思路：
后序遍历的顺序是 : 左子树 | 右子树 | 根节点。
二叉搜索树的性质：左子树的值都小于根节点，右子树的值都大于根节点。
采用递归分治的方式将数划分为左右子树，然后递归检查每个子树的正确性（是否满足后序遍历和二叉搜索树的性质。）
递归的流程：
1）划分左右子树：遍历数组 postorder 区间 [i, j]，逐个元素与根节点 postorder[j] 比较，寻找大于根节点的值的下标 m，此时区间 [i, m-1] 为左子树，[m, j-1] 为右子树。
2）检查左右子树是否满足二叉搜索树的性质（左子树的元素小于根节点，右子树的元素大于根节点），因为左子树 [i, m -1] 在寻找大于根节点的值的下标 m 时已经检查过了，所以只需检查右子树 [m, j-1] 的元素是否大于根节点。
3）递归检查左右子树的正确性（满足后序遍历和二叉搜索树的性质）。
递归结束的条件：i >= j，也就是子树中的节点数量小于等于1时，此时无需检查，返回 true。
class Solution {
public boolean verifyPostorder(int[] postorder) {
return checkout(0, postorder.length-1, postorder);
}
private boolean checkout(int i, int j, int[] postorder){
if(i >= j)
return true;
int m = j; //如果全部元素都小于根节点，也就是没有右子树，[i, m-1]就是左子树，之前错放在 j-1 位置上。
// 划分左右子树
for(int k = i; k < j; k ++){
if(postorder[k] > postorder[j]){
m = k;
break;
}
}
// 检查右子树的元素是否都大于根节点
for(int k = m; k < j; k ++)
if(postorder[k] <= postorder[j])
return false;
// 检查左右子树是否满足后序遍历的性质和二叉搜索树的性质
return checkout(i, m-1, postorder) && checkout(m, j-1, postorder);
}
}
代码优化:
int m = j;
//划分左右子树
for(int k = i; k < j; k ++){
if(postorder[k] > postorder[j]){
m = k;
break;
}
}
可以改为
int m = 0;
while(postorder[m] < postorder[j])
m++;
