我好久没更新了 原因是我登不上账号了..
题目：
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回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))
}
