综合文章

# 二叉搜索树的后序遍历序列📕

# 题目描述

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

# 解题思路

  1. 搜索二叉树的特点：左子树的值一定小于根节点的值，右子树的值一定大于根节点的值；
  2. 后序遍历的特点：最后一个元素一定是根元素，排列的顺序是[左子树][右子树][根节点]。

例如🌰：

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

# coding

解法一

  • 传递进来数组的最后一项是根节点，把它从数组中pop()出来
  • 然后可以用findIndex()查找出数组中大于根节点的那个下标rightIdx，这个下标就是左子树和右子树的分割下标
  • 在下标左边为左子树，下标及下标右边为右子树
  • 利用数组的every()判断左子树的每一项是不是都小于根节点，同理判断右子树的每一项是不是都大于根节点
/*
* 判断某个数组是不是某搜索二叉树的后序遍历结果
* 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
阅读全文

← 二叉搜索树的第k个节点 →