题目描述

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

参考以下这颗二叉搜索树：

  1.  5<br />    / \<br />   2   6<br />  / \<br /> 1   3<br />示例 1：

输入: [1,6,3,2,5]
输出: false
示例 2：

输入: [1,3,2,6,5]
输出: true

提示：

数组长度 <= 1000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

/**
 * @param {number[]} postorder
 * @return {boolean}
 */
var verifyPostorder = function(postorder) {
    let len = postorder.length;
    if (len <= 1) return true;
    let root = postorder[len - 1];
    // 初始化分界线在 root 的位置
    let rightIdx = len - 1;
    // 往左找分界线，找到小于 root 的值或到了边界
    while (rightIdx > 0 && postorder[rightIdx - 1] > root) {
        rightIdx--;
    }
    // 检查左子树是否合乎规则，左子树所有节点都应小于 root
    for (let i = 0; i < rightIdx; i++) {
        if (postorder[i] >= root) return false;
    }
    // 没有左/右子树了
    if (rightIdx <= 0 || rightIdx === len - 1) {
        return verifyPostorder(postorder.slice(0, len - 1));
    }
    // 递归判定左子树和右子树是否都满足
    return verifyPostorder(postorder.slice(0, rightIdx - 1)) && verifyPostorder(postorder.slice(rightIdx, len - 1));
};

单调栈。有点难。

/**
 * @param {number[]} postorder
 * @return {boolean}
 */
var verifyPostorder = function(postorder) {
    let stack = [];
    let root = Number.MAX_SAFE_INTEGER;
  console.log(`postorder:${JSON.stringify(postorder)}`);
  for (let i = postorder.length - 1; i >= 0; i--) {
    console.log(`postorder[i]:${postorder[i]}, stack:${JSON.stringify(stack)}, root:${root}`);
    // 左子树节点不能大于根节点
    if (postorder[i] > root) return false;
    // 当触发递减时，到栈里往回找递减节点的根节点
    while (stack.length && stack[stack.length - 1] > postorder[i]) {
      // 不断地更替根节点直到找到为止，找到根节点是为了接着往下判定其是否还在其左子树
      root = stack.pop();
      console.log(`stack.pop - postorder[i]:${postorder[i]}, stack:${JSON.stringify(stack)}, root:${root}`);
    }
    // 节点存起来，为了后面到递减时往回找递减节点的根节点
    stack.push(postorder[i]);
  }
  return true;
};

image.pngimage.png