# 二叉搜索树的后序遍历序列📕
# 题目描述
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
# 解题思路
- 搜索二叉树的特点：左子树的值一定小于根节点的值，右子树的值一定大于根节点的值；
- 后序遍历的特点：最后一个元素一定是根元素，排列的顺序是
[左子树][右子树][根节点]。
例如🌰：
[1, 5, 4, 3, 2]; // true 左子树: [1],右子树: [5,4,3], 根节点: 2
[1, 5, 2, 4, 3]; // false
@前端进阶之旅: 代码已经复制到剪贴板
# coding
解法一
- 传递进来数组的最后一项是根节点，把它从数组中
pop()出来 - 然后可以用
findIndex()查找出数组中大于根节点的那个下标rightIdx，这个下标就是左子树和右子树的分割下标 - 在下标左边为左子树，下标及下标右边为右子树
- 利用数组的
every()判断左子树的每一项是不是都小于根节点，同理判断右子树的每一项是不是都大于根节点
/*
* 判断某个数组是不是某搜索二叉树的后序遍历结果
* 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(
