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

题目描述:输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出 Yes,否则输出 No。假设输入的数组的任意两个数字都互不相同。

# 题目描述

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

# 思路

这题主要考察的是后序遍历的特点和二叉搜索树的特点。根据定义,后序遍历结果的最后一个元素就是当前二叉树的根元素。结合二叉搜索树 左子节点 > 根节点 > 右子节点 的特点,我们可以找到左右子树的元素。

例如下面这个二叉搜索树:

它的后序遍历顺序是:2,7,9,12,11,8。所以整体的解决思路是:

  • 最后一个元素是根节点:8
  • 因为左子树都小于根节点,从头开始遍历可以找到左子树:2、7。
  • 剩下的元素就是右子树:9、12、11。
  • 再分别递归检查左右子树是否满足后序遍历顺序

# 代码实现

/**
 * @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))
  );
}

# 更多资料