题解 | #二叉搜索树的后序遍历序列#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 
 * @param sequence int整型一维数组 
 * @return bool布尔型
 */
export function VerifySquenceOfBST(sequence: number[]): boolean {
    // write code here
    //找出根节点，然后区分左树和右树，当左子树出现大于根节点的就不合法，右子树出现小于 根节点的也不合法，一直这样分治下去来进行判断
    const size = sequence.length
    //空树不是搜索树
    if(size == 0){
        return false
    }
    //一个函数来进行判断左树中是否有一个值大于根节点
    return checkVaild(sequence,0,size-1)
}
const checkVaild = (array,start,end):boolean=>{
    //当子树只有一个节点
    if(start >= end)return true
    //找到根节点
    const root = array[end]
    //区分左右子树
    let j = end - 1
    while(j >=0 && array[j] > root)j--;
    //检查左子树是否存在大于根节点的
    for(let i = start;i <= j;i++){
        if(array[i] > root){
            return false
        }
    }
    //分治来检查左子树和右子树
    return checkVaild(array,start,j) && checkVaild(array,j +1,end-1)
}