剑指Offer JZ23 二叉搜索树的后序遍历序列（JavaScript：递归）

时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M 热度指数：767662
本题知识点： 栈 树

题目描述
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true,否则返回false。假设输入的数组的任意两个数字都互不相同。（ps：我们约定空树不是二叉搜素树）
示例1
输入
[4,8,6,12,16,14,10]
返回值
true

思路：利用后序遍历和二叉搜索树的规律，父节点在最后一个元素，且左子节点小于父节点，右节点大于父节点。将数组进行切割出左右子树，递归。
若长度为0，则递归结束，符合要求，返回true
若左子树切割完，右子树内的元素有小于父节点的，则不符合要求，返回false

function VerifySquenceOfBST(sequence)
{
    // write code here
    if(sequence.length === 0) return false
    return sub(sequence)
}

function sub (sequence){
    let len = sequence.length
    let target = sequence[len-1]
    let i = 0,index = 0
    while(i < sequence.length -1 ){
        if(sequence[i]<target){
            i++
        }
        else if(sequence[i]>target){
            index = i
            while(i<sequence.length-1){
                i++
                if(sequence[i]<target) return false
            }
        }
    }
    if(sequence.length === 0) return true
    return sub(sequence.slice(0,index)) && sub(sequence.slice(index,len-1))
}

最后

以上就是聪明耳机为你收集整理的剑指Offer JZ23 二叉搜索树的后序遍历序列（JavaScript：递归）的全部内容，希望文章能够帮你解决剑指Offer JZ23 二叉搜索树的后序遍历序列（JavaScript：递归）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。