题解 | #二叉搜索树的后序遍历序列#

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence == null || sequence.length == 0) {
            return false;
        }
        return verify(sequence, 0, sequence.length - 1);
    }
    private boolean verify(int[] arr, int first, int last) {
        if(last - first <= 1) {
            return true;
        }
        int rootVal = arr[last];
        int riFirst = first;
        for(; riFirst < last; riFirst++) {
            if(arr[riFirst] > rootVal) {
                break;
            }
        }
        for(int i = riFirst + 1; i < last; i++) {
            if(arr[i] < rootVal) {
                return false;
            }
        }
        return verify(arr, first, riFirst - 1) && verify(arr, riFirst, last - 1);
    }
}