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

对于二插搜索树BST的后续遍历正确合法序列，必须满足对于一个序列，最后一个元素x一定是根， 然后如果去掉最后一个元素得到的新的序列为T，那么T就满足：T可以分成两段，前一段为左子树 小于x，后一段右子树大于x，且这两段（子树）也必须是合法的搜索树后续遍历序列

function VerifySquenceOfBST(sequence)
{
    // write code here
    if(sequence.length == 0) return false
//     对于二插搜索树BST的后续遍历正确合法序列，必须满足对于一个序列，最后一个元素x一定是根，
//     然后如果去掉最后一个元素得到的新的序列为T，那么T就满足：T可以分成两段，前一段为左子树
//     小于x，后一段右子树大于x，且这两段（子树）也必须是合法的搜索树后续遍历序列
    return judgeBST(0, sequence.length - 1)
    function judgeBST(start, end){
        if(start >= end){
//             子树遍历结束，说明此子序列符合BST二叉树后续遍历序列
            return true
        }
//         先找出第一个比sequence[end]大的元素索引
        let index = end
        for(let i = start; i < end; i++){
            if(sequence[i] > sequence[end]){
                index = i
                console.log(index)
                break
            } 
        }
//         然后判断后面那一段子序列是否都比sequence[end]大，如果一旦有一个比它小，则它就不是一个后续遍历序列，直接返回false
        for(let i = index + 1; i < end; i++){
            if(sequence[i] < sequence[end]){
                return false
            }
        }
//         如果满足以上条件，则就需要递归查找并判断sequence[end]为根节点的左右子树
        return judgeBST(start, index-1) && judgeBST(index, end - 1)
    }
    
    
    
}
module.exports = {
    VerifySquenceOfBST : VerifySquenceOfBST
};