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]))