二叉搜索树的后序遍历序列|博客系列

[1, 5, 4, 3, 2]; // true 左子树: [1],右子树: [5,4,3], 根节点: 2
[1, 5, 2, 4, 3]; // false

/*
* 判断某个数组是不是某搜索二叉树的后序遍历结果
* param {Array} 
* return {Boolean}
*/
function isBST (postOrder) {
  let isBSTFn = function (postOrder) {
    // 若长度为0 则也判断为true
    if (postOrder.length === 0) {
        return true;
    }
    let res = true;
    if (postOrder) {
      let root = postOrder.pop(); // 根节点
      let rightIdx = postOrder.findIndex(item => item > root);
      let left = postOrder.splice(0, rightIdx);
      let right = postOrder;
      if (left) {
        res = left.every(item => item < root);
      }
      if (right) {
        res = right.every(item => item > root);
      }
    }
    return res;
  }
  return isBSTFn(postOrder)
}
console.log(isBST([5, 4, 3, 2, 1])); // true 左子树: [], 右子树: [5,4,3,2], 根节点: 1
console.log(isBST([1, 5, 4, 3, 2])); // true 左子树: [1],右子树: [5,4,3], 根节点: 2
console.log(isBST([1, 5, 2, 4, 3])); // false

/*
* 判断某个数组是不是某搜索二叉树的后序遍历结果
* param {Array} 
* return {Boolean}
*/
function isBST (postOrder) {
    // 若长度为0 则也判断为true
    if (postOrder.length === 0) {
        return true;
    }
    const len = postOrder.length
    let root = postOrder[len - 1], // 最后一位为根节点的值
    i, // 左子树的最后一位的下标
    j; // 右子树的第一位的下标
    
    for (i = 0; i < len - 1 && postOrder[i] < root; ++i);
    for (j = i; j <len - 1 && postOrder[j] > root; ++j);

    if (j !== len - 1) { // 若还未遍历完，则说明不是左边部分小，右边部分大，不符合后序遍历
        return false;
    }

    let left = isBST(postOrder.slice(0, i)); // 继续遍历左子树
    let right = isBST(postOrder.slice(i, len - 1));

    return left && right;
}
console.log(isBST([5, 4, 3, 2, 1])); // true 左子树: [], 右子树: [5,4,3,2], 根节点: 1
console.log(isBST([1, 5, 4, 3, 2])); // true 左子树: [1],右子树: [5,4,3], 根节点: 2
console.log(isBST([1, 5, 2, 4, 3])); // false