递归
以上面这课二叉搜索树为例其后续遍历结果为[5,7,6,9,11,10,8]。可以知道数组的最后一个元数8是二叉树的根节点。二叉搜索树的左子树节点小于根节点，右子树大于根节点，所以数组[5,7,6,9,11,10,8]可以被分为两部分：[5，7，6]、[9，11，10]。这两部分又是一个二叉搜索树所以可以使用递归进行判断。
再来分析[7,4,6,5]这个序列，5为根节点由于7大于5所以这个二叉搜索树无左子树，所以其右子树[7,4,6]应大于5，二其中4小于5所以这个序列不是二叉搜索树的后续遍历。
经过以上分析后代码如下：
class Solution {
public boolean verifyPostorder(int[] postorder) {
return verifyPostorder(postorder, postorder.length);
}
private boolean verifyPostorder(int[] postorder, int length){
if(postorder == null || length <= 0)
return true;
int root = postorder[length - 1];//根节点为数组最后一个节点
int i = 0;
//二叉搜索树的左子树节点都小于根节点
while(i < length - 1){
if(postorder[i] > root)
break;
++i;
}
int j = i;
//二叉搜索树的右子树节点都大于根节点
while(j < length - 1){
if(postorder[j] < root)
return false;
++j;
}
//判断左子树是否为二叉搜索树
boolean left = true;
if(i > 0)
left = verifyPostorder(postorder,i);
//判断右子树是否为二叉搜索树
boolean right = true;
if(i < length - 1)
right = verifyPostorder(Arrays.copyOfRange(postorder,i,j), length - 1 - i);
return left && right;
}
}