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

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

    }

    private boolean verifySection(int[] sequence, int start, int end) {
        if (start >= end) return true;
        int mid = sequence[end];
        int midIndex = end;
	    // 先遍历比根大的值在什么位置
        for (int i = start; i < end; i++) {
            if (sequence[i] > mid) {
                midIndex = i;
                break;
            }
        }
	  	// 以大的位置开始遍历到根中间是否有比根小的，有则不是，否则继续递归细分的段判断。
        for (int i = midIndex; i < end; i++) {
            if (sequence[i] < mid) return false;
        }
        return verifySection(sequence, start, midIndex - 1) &&
               verifySection(sequence, midIndex, end - 1);
    }
}

解题思想：特性：前面元素有一部分大于或小于最后一个根节点元素，如果在小于的部分找到了大于的或者大于的部分找到了小于的则不是后续遍历二叉搜索树。