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

> 本文详细讲解如何判断一个整数数组是否为二叉搜索树的后序遍历序列，分析二叉搜索树和后序遍历的特性，并提供JavaScript代码实现及解题思路，适合前端面试和数据结构学习。

- 原文：https://feinterview.poetries.top/docs/fe-blog-docs/blog-docs/data-struct/11-%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E7%9A%84%E5%90%8E%E5%BA%8F%E9%81%8D%E5%8E%86%E5%BA%8F%E5%88%97
- 来源：前端进阶之旅（feinterview.poetries.top）
- 更新：2025.10.25

---

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

### 题目描述

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

### 解题思路

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

例如🌰：

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

### coding

**解法一**

- 传递进来数组的最后一项是根节点，把它从数组中`pop()`出来
- 然后可以用`findIndex()`查找出数组中大于根节点的那个下标`rightIdx`，这个下标就是左子树和右子树的分割下标
- 在下标左边为左子树，下标及下标右边为右子树
- 利用数组的`every()`判断左子树的每一项是不是都小于根节点，同理判断右子树的每一项是不是都大于根节点

```javascript
/*
* 判断某个数组是不是某搜索二叉树的后序遍历结果
* 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
```

**解法二**

```javascript
/*
* 判断某个数组是不是某搜索二叉树的后序遍历结果
* 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
```
