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

// 判断一个数组是不是一个二叉搜索树的后序遍历的结果 等价于 判断一个数组是不是满足这个特性：
// 最后一个元素为根节点，某个元素之前所有元素都小于根节点，之后所有元素都大于根节点，并且以根节点大小为界分成的左右两部分仍然符合这个特点。
function VerifySquenceOfBST(sequence) {
    if (sequence.length === 0) {
        return false;// 约定空树不是二叉搜索树
    }
    return verify(sequence);
}
function verify(arr) {// 上帝写好的函数，它能判断一个数组是不是一个二叉搜索树的后序遍历的结果
    if (arr.length <= 1) { //特殊情况： 空树或只有一个节点的树一定是二叉搜索树
        return true;
    }

    //特殊情况：判断整个数组是不是满足这个特性
    let rootIndex = 0;
    let rootValue = arr[arr.length - 1];

    while (arr[rootIndex] < rootValue) {
        rootIndex++;
    }

    let temp = rootIndex;

    while (temp < arr.length) {
        if (arr[temp] < rootValue) {
            return false;
        }
        temp++;
    }
    //执行到这里还没return false说明整体是满足的
    
    let left = verify(arr.slice(0, rootIndex));
    let right = verify(arr.slice(rootIndex, arr.length - 1));
    return left && right;//return 左右两边是否满足
}
module.exports = {
    VerifySquenceOfBST: VerifySquenceOfBST
};