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

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 
 * @param sequence int整型一维数组 
 * @return bool布尔型
 */
export function VerifySquenceOfBST(sequence: number[]): boolean {
    // write code here
    if(sequence.length == 0){
        return false;
    }
    return son(sequence, 0, sequence.length - 1);
}
export function son(sequence: number[], first: number, last:number): boolean {
    if (last - first <= 1)
        return true;
    let split: number = first;
    while(split < last && sequence[split] < sequence[last]){
        split ++;
    }
    for(let i: number = split; i < last; i ++) {
        if(sequence[i] < sequence[last]){
            return false;
        }
    }
    return son(sequence, first, split - 1) && son(sequence, split, last - 1);
}