二叉搜索树的后序遍历序列

题目描述

示例

代码

代码1 递归（分治）

/*
分治，递归判断
判断数组是否是后序遍历的二叉搜索树，后序遍历（左右根），根在最后
二叉搜索树满足 左节点的值 < 根节点的值 < 右节点的值
所以可以每次从数组的末尾拿一个根出来，然后根据根的大小，把数组前面的值分为左子树和右子树
然后继续重复这样的操作，当右子树的值小于根节点时，那就不符合二叉搜索树
*/

function VerifySquenceOfBST(sequence)
{
    // 题目要求空树不是二叉搜索树
    if(!sequence || sequence.length === 0) return false
    
    // 分治求解
    return vertify(sequence, 0, sequence.length - 1 )
    
    
    // 用来递归判断是否符合二叉搜索树 返回true或false
    // start表示起始位置
    // rootIndex表示根所在的位置索引
    function vertify(sequence, start, rootIndex) {
        // 出口
        // 当rootIndex <= start 表示剩一个节点，校验到最后了
        if(rootIndex <= start) return true
        
        // 开始分治，根据末尾的根节点，找左、右子树
        let i = 0 // 左右子树的分割点的索引
        for(; i < rootIndex; i++ ){
            // 当找到一个比根还大的值时，说明是右子树的开始，停止循环，记录这个位置
            if(sequence[i] > sequence[rootIndex]) {
                break;
            }
        }
        
        // 在右子树中，判断有没有比根节点还小的值，如果有，那就不是二叉搜索树，返回false
        for(let j = i; j < rootIndex; j++){
            if(sequence[j] < sequence[rootIndex]){
                return false
            }
        }
        
        
        // 如果上面这一次循环都符合，那继续缩小规模，分治
        let leftTree = sequence.slice(0, i)
        let rightTree = sequence.slice(i, sequence.length-1)
        return vertify(leftTree, 0, leftTree.length-1) && vertify(rightTree, 0, rightTree.length-1)
    }
}

时间复杂度为O(N^2)：当二叉搜索树是一个链表时，递归N次，每次也需要比较N次，所以时间复杂度最坏情况为O(N^2)

空间复杂度O(n),：当树为链式结构时, 递归深度为n

题目来源

JZ33 二叉搜索树的后序遍历序列