JZ23 二叉搜索树后序遍历序列，分治思想

（代码直接拉到底）
首先明确一下，后序遍历时，一棵子树的元素是连续的。所以我们可以用两个整形变量left, right框定它们在sequence上对应的序号范围。

构造子函数，参数为

• int[] sequence，不解释
• Integer min, 该段数组(sequence[left]--sequence[right])对应子树的数值下界
• Integer max, 该段数组(sequence[left]--sequence[right])对应子树的数值上界
• int left，数组左边界
• int right，数组右边界

接下来要做的事情就是检查sequence[left]--sequence[right]是不是落在了(min, max)这范围之间。

以下是关于代码的FAQ
Q：为什么一开始传入min, max的值为null？
A：因为一开始我们的确不知道上下界是什么所以空在哪里。上下界将在递归过程中由它们的根结点值决定。
Q：为什么用min和max用Integer而不是int？
A：看似好像用int也可以，只要一开始输入 Integer.MIN_VALUE和Integer.MAX_VALUE，也就行了？注意，这里每一个节点的值都是不同的。所以 11/12 行代码中的“=”是不能省略的。既然如此，如果输入的时候 给你一个值为Integer.MIN_VALUE的节点呢？ 这就直接返回false了--当然可以再加入两个全局的boolean变量做判断，但没必要。
Q：每次需要比较sequence[left]--sequence[right]所有right-left+1个值吗？
A：不需要。这里采取分治思想，比较根节点就足够了。
Q：if(left>right) return true;是干嘛用的？
A：这意味着对应的是一棵空树了，它可以由最后left==right的情况进一步递归得到。（所以不写这个，递归就会数组越界或死循环。）

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence==null||sequence.length==0) return false; 
        return verify(sequence,null,null,0,sequence.length-1);
    }

    boolean verify(int[] sequence, Integer min, 
                   Integer max, int left, int right){
        if(left>right) return true;
        int mid=sequence[right];
        if(min!=null&&min>=mid) return false;
        if(max!=null&&max<=mid) return false;        
        int i=left;
        for(; i<right; i++){
            if(sequence[i]>mid) break;
        }
        return verify(sequence, min, mid, left, i-1)&&
            verify(sequence, mid, max, i, right-1);
    }
}