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

思路：

1、末尾为根节点，左子树小于根节点，右子树大于根节点，找到左、右子树分界点，左子树中存在大于根节点的，则False

2、递归判断左、右子树数组是否同样满足

注意：

1、初始节点如果列表为空，则返回False

2、判断函数中，若递归判断到空列表，则返回True

class Solution:
    def VerifySquenceOfBST(self , que: List[int]) -> bool:
        # write code here
        
        if len(que) == 0:
            return False
        
        return self.check(que)

    def check(self, que):
        if len(que) == 0:
            return True
        
        root = que[-1]
        j = len(que) - 1
        while j >= 0 and que[j] >= root:
            j -= 1
            
        for i in range(0, j+1):
            if que[i] > root:
                return False
        
        return self.check(que[:j+1]) and self.check(que[j+1:-1])