面试题33：二叉搜索树的后序遍历序列

题目：输入一个整数数组，判断该数组是否是某二叉搜索树的后序遍历结果。如果是返回true，不是返回false。假设输入的数字任意两个数字不相同。例如输入数组{5,7,6,9，11,10,8}，则返回true；如果输入的数组是{7,4,6,5}，则返回false。

图片1

public static boolean verify(int[] array,int beginIndex,int endIndex) {

if (array ==null || beginIndex <0 || beginIndex >= array.length || endIndex >= array.length || beginIndex >= endIndex)return false;

    int leftChildIndex = -1;

    for (int i = beginIndex;i < endIndex;i++) {

        if (array[i] < array[endIndex])leftChildIndex =i;

        else break;

    }

for (int i = (leftChildIndex == -1 ? beginIndex :leftChildIndex +1);i < endIndex;i++)if (array[i] <= array[endIndex])return false;

    boolean result =true;

    if (leftChildIndex != -1 &&leftChildIndex - beginIndex >=2)result =result &&verify(array,beginIndex,leftChildIndex);

    if (leftChildIndex != -1 && (endIndex -1) - (leftChildIndex +1) >=2)result =result &&verify(array,leftChildIndex +1,endIndex -1);

    if (leftChildIndex == -1 && (endIndex -1) - beginIndex >=2)result =result &&verify(array,beginIndex,endIndex -1);

    return result;

}