AcWing 46. 二叉搜索树的后序遍历序列-JavaScript
原题链接
简单
作者:
semicloud
,
2024-02-19 08:25:25
,
所有人可见
,
阅读 27
/**
* @param {number[]} sequence
* @return {boolean}
*/
var verifySequenceOfBST = function(sequence) {
// 如果 root 为 null 或只有 1 个节点,则必为 BST
if ([0, 1].includes(sequence.length)) return true;
// 数组最后一个元素必为根节点
const root = sequence[sequence.length - 1];
// 找到左右子树的分界点
// 因为是 BST,因此整个数组必然可以被根节点分为两部分
// 前一部分都小于根节点的值,后一部分都大于根节点的值
const idx = sequence.findIndex((x) => x > root);
// 获取左、右子树数组
const leftSequence = sequence.slice(0, idx);
// 获取右子树时忽略 root 节点
const rightSequence = sequence.slice(idx, -1);
// 递归判断左右子树是否为 BST
const isLeftBST = verifySequenceOfBST(leftSequence);
const isRightBST = verifySequenceOfBST(rightSequence);
// 判断以 root 为根节点的二叉树是否是 BST:左子树上的值都小于 root,右子树上的值都大于 root
const isCurBST = leftSequence.every((x) => x < root) &&
rightSequence.every((x) => x > root);
// 左子树、右子树以及当前的树都是 BST,因此整棵树就是 BST
return isLeftBST && isRightBST && isCurBST;
};