题目描述

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

提示：

• 数组长度 <= 1000
• 参考以下这颗二叉搜索树：

     5
    / \
   2   6
  / \
 1   3

测试用例

用例1 ；

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

用例2

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

思路

递归

二叉搜索树特点如下

1. 若任意结点的左子树不为空，则该结点左子树上所有节点的值都不大于其根节点的值
2. 若任意结点的右子树不为空，则该结点右子树上所有节点的值都不小于其根节点的值

思路就是递归判断左子树是否都不大于root同时右子树是否都大于root，每次要先拿到根节点，根据根节点来拿到左子树和右子树，然后进行判断

代码实现

/**
 * @param {number[]} postorder
 * @return {boolean}
 */

var __readline = require("readline-sync");
__readline.setDefaultOptions({ prompt: "" });
var readline = __readline.prompt;

console.log("请输入后序遍历序列: ");
const postorder = readline().split(" ").map(Number);

var verifyPostorder = function (postorder) {
  // 后序遍历
  // 二叉搜索树特点如下
  // 1. 若任意结点的左子树不为空，则该结点左子树上所有节点的值都不大于其根节点的值
  // 2. 若任意结点的右子树不为空，则该结点右子树上所有节点的值都不小于其根节点的值

  // 思路就是判断左子树是否都不大于root同时右子树是否都大于root
  if (postorder.length <= 2) {
    return true;
  }

  // 拿到根节点
  const root = postorder.pop();

  let i = 0;

  // 首先找到左右子树的分界点
  while (postorder[i] < root) {
    i++;
  }
  // 拿到右子树
  let rightTree = postorder.slice(i);
  // 右子树当中所有节点都应该大于root
  const rightRes = rightTree.every((item) => item > root);

  // 递归判断左右子树
  return (
    rightRes &&
    verifyPostorder(postorder.slice(0, i)) &&
    verifyPostorder(rightTree)
  );
};

const res = verifyPostorder(postorder);
console.log("结果为: ", res);

/* 
  请输入后序遍历序列:
  1 6 3 2 5
  结果为:  false
  请输入后序遍历序列:
  1 3 2 6 5
  结果为:  true
 */