二叉搜索树的后序遍历

我好久没更新了 原因是我登不上账号了..

题目：

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

例子：

输入: [4,8,6,12,16,14,10]
输出： true

我其实对后序遍历的规律已经不记得了 所以看了一下题解 大佬们总结的好到位：

二叉搜索树的后序遍历判断：
1、首先明白二叉搜索树的特点，左节点小于根，右节点大于根，左右子树也同样是二叉搜索树
2、根据二叉搜索树的特点，我们发现需要递归的判断，根节点肯定在数组的末尾
3、找出比根节点小的就是左子树，找到比根节点大的就是右子树
4、如果左右子树中有不满足的条件的元素则返回或者结束判断
5、直到所有元素都判断完则满足二叉搜索树的特点，或者中途返回

根据大佬们总结的规律 我用JS实现了出来

function VerifySquenceOfBST(sequence)
{
    // write code here
   if(sequence.length === 0) {
        return false
    }
    if(sequence.length === 1) {
        return true
    }
    var root = sequence[sequence.length - 1]
    var i = 0
    //找到第一个大于根节点的节点 记录好位置
    while(sequence[i] < root) {
        i++
    }
    //将原数组拆分成左子树和右子树
    const leftarr = sequence.slice(0, i)
    const rightarr = sequence.slice(i, sequence.length - 1)
    //遍历右子树 如果有小于root的 则说明不符合后序遍历的规律
    for(let a = 0; a <= rightarr.length - 1; a++) {
        if(rightarr[a] < root) {
            return false
        }
    }
    // 将左子树和右子树放入该函数去查看是否符合后序遍历规律  &结果即是最后的结果
    return (leftarr.length === 0 ? true : VerifySquenceOfBST(leftarr)) && (rightarr.length === 0 ? true : VerifySquenceOfBST(rightarr))
}