剑指offer - 二叉搜索树的后续遍历序列 - JavaScript

/**
 * @param {number[]} sequence
 * @return {boolean}
 */
function verifyPostorder(sequence) {
    const length = sequence.length;
    if (length < 2) return true;

    const root = sequence[length - 1];
    // sequence[0, root) 是左子树；sequence[root, length - 1)是右子树
    let cut = 0; // 左子树节点的数量
    for (; cut < length - 1 && sequence[cut] < root; ++cut) {}
    // 这里要检查右子树中的值是否满足条件
    for (let i = cut; i < length - 1; ++i) {
        if (sequence[i] < root) {
            return false;
        }
    }

    return (
        verifyPostorder(sequence.slice(0, cut)) &&
        verifyPostorder(sequence.slice(cut, length - cut - 1))
    );
}