二叉搜索树的后序遍历

二叉搜索树的后续遍历的序列中最后一个数字为根节点，而前面的数字，比根节点小的在左边，比根节点大的在右边。
这个左边右边的界限要用一个一个数字和根节点进行比较得出，可能左子树不存在，也有可能右子树不存在。
我们循环遍历后序遍历结果的数组，找到比根节点大的第一个点，然后如果这个点后面的数字还有比根节点小的，那么这个后序遍历就不是二叉搜索树的。如果后面没有数字比根节点小，则把左子树和右子树继续进行上述操作，全部操作完成后都满足条件即为二叉搜索树的后序遍历。

public class Solution {
    public boolean f(int [] sequence, int start, int end){
        if(start>=end){
            return true;
        }
        int root = sequence[end];
        int index = 0;
        int flag = 0;
        for(int i=start;i<end;i++){
            if(flag==0&&sequence[i]>root){
                flag = 1;
                index = i;
                break;
            }
        }

        // flag如果还等于0，那么前面的数字均小于root，则只有左子树
        // 如果index等于零，说明第一个就大于root，则只有右子树
        // 主要是检验右子树是否有比root小的数字，如果有，则返回false
        if(flag==1){
            for(int i=index;i<end;i++){
                if(sequence[i]<root){
                    return false;
                }
            }
            boolean b1 = f(sequence, start, index-1);
            boolean b2 = f(sequence, index, end-1);
            return b1&&b2;
        }else {
            boolean b1 = f(sequence, start, end-1);
            return b1;
        }

    }

    public boolean VerifySquenceOfBST(int [] sequence) {
        int l = sequence.length;
        if(l==0){
            return false;
        }
        return f(sequence, 0, l-1);
    }
}