1. 题目描述

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

2. 思路描述

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

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

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

3. 代码实现

/**
 * 判断是否是二叉搜索树的后序遍历结果
 * @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]));
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