题目描述

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

题解

若一个树为一个二叉搜索树，则它左子树上的节点一定比根节点小，右子树上的节点一定比根节点大，且它的左右子树一定也为二叉搜索树。

解题思路：

首先找到左子树和右子树的开始坐标和结束坐标，得到左子数组和右子数组。
验证左子数组中的元素是否都小于根节点，右子数组中的元素是否都大于根节点。
若满足条件，则进行递归验证左子树和右子树是否都是二叉搜索树（利用'或'门的短路性质，子树为空不进行判断）。

给出两种实现方法：

public boolean VerifySequenceOfBST(int[] sequence) {
    if (sequence.length == 0)
        return false;
    int len = sequence.length;
    int root = sequence[len-1];
    int leftBegin = 0, leftEnd = 0;

    // 找左子树的开始坐标和结束坐标
    while (leftEnd < len-1) {
        if (sequence[leftEnd] > root)
            break;
        leftEnd++;
    }
    // 找右子树的开始坐标和结束坐标
    int rightEnd = leftEnd, rightBegin = leftEnd;
    while (rightEnd < len-1) {
        if (sequence[rightEnd] < root)
            return false;
        rightEnd++;
    }
    // 得到子数组
    int[] leftArr = Arrays.copyOfRange(sequence, leftBegin, leftEnd);
    int[] rightArr = Arrays.copyOfRange(sequence, rightBegin, rightEnd);
    
    // 验证左右子树上的节点是否满足二叉搜索树的规则，不满足直接返回false
    for (int num : leftArr)
        if (num > root) return false;
    for (int num : rightArr)
        if (num < root) return false;

    boolean left = leftArr.length == 0 || VerifySequenceOfBST(leftArr);
    boolean right = rightArr.length == 0 || VerifySequenceOfBST(rightArr);
    return left && right;
}

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

public boolean VerifySequenceOfBST(int[] sequence, int left, int right) {
    // 当子树为空或子树只有一个节点时，直接返回true
    if (left >= right)
        return true;
    int i = right;
    // 找到右子树的起点i
    while (i > left && sequence[i-1] > sequence[right])
        i--;
    // 从左子树的终点开始，验证左子树是否小于根节点
    for (int j = i-1; j >= left; j--) {
        if (sequence[j] > sequence[right])
            return false;
    }
    return VerifySequenceOfBST(sequence, left, i-1) && VerifySequenceOfBST(sequence, i, right-1);
}