剑指Offer——二叉搜索树的后序遍历序列（JS实现）

var verifyPostorder = function(postorder) {
    // !本题的解题关键：二叉搜索树的后序遍历，最后一个元素是根节点
    // 如果输入的数组长度小于2，则返回true
    let len = postorder.length;
    if (len < 2) return true;
    // 区分左右子树 
    let flag = 0;
    // 找到根节点
    let root = postorder[len-1];
    for (let i = 0; i < postorder.length;i++) {
        if (postorder[i] > postorder[len-1]) {
            flag = i;
            break;
        }
        if (i === len-1) {
            flag = i;
        }
    }
    // 左子树
    let leftTree = postorder.slice(0,flag);
    // 右子树
    let rightTree = postorder.slice(flag,len-1);
    // 如果右子树的每一个节点都大于根节点，则继续递归判断，反之为false
    if (rightTree.every((value) => value > root)) {
        return verifyPostorder(leftTree) && verifyPostorder(rightTree);
    } else {
        return false;
    }
};