1. 题目描述

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

2. 思路描述

因为是后序遍历，所以根节点是最后一个元素。然后前面序列分为 2 部分，有一部分是左子树，有一部分是右子树。

根据二叉搜索树的性质，左子树的元素一定小于最后一个元素，右子树的元素一定大于最后一个元素。

根据这个思路，一直递归下去即可。只要所有部分都满足二叉搜索树的性质，那么符合条件。

3. 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
 * 判断是否是二叉搜索树的后序遍历结果
 * @param {Array} tailOrder 后序遍历顺序
 */
function isBST(tailOrder) {
    // 空序列代表空树, 这里认为是BST
    if (tailOrder.length === 0) {
        return true
    }

    const length = tailOrder.length
    let root = tailOrder[length - 1],
        i,
        j

    // 找到左子树
    for (i = 0; i < length - 1 && tailOrder[i] < root; ++i);
    // 找到右子树
    for (j = i; j < length - 1 && tailOrder[j] > root; ++j);

    // 如果没有遍历完, 说明不是左边部分小，右边部分大的分布
    // 显然，不符合后序遍历的定义
    if (j !== length - 1) {
        return false
    }

    // 处理左右子树
    let left = isBST(tailOrder.slice(0, i))
    let right = isBST(tailOrder.slice(i, length - 1))

    return left && right
}

/**
 * 以下是测试代码
 */
console.log(isBST([5, 7, 6, 9, 11, 10, 8]))
console.log(isBST([4, 3, 2, 1]))
console.log(isBST([7, 4, 6, 5]))