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
|
function isBST(tailOrder) { 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]))
|