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

class Solution:
    def VerifySquenceOfBST(self, sequence):
        # write code here
        if not sequence:
            return False
        if len(sequence)==0:
            return False
        def check(se):

            if len(se) <=2:
                return True
            root = se[-1]
            pos = len(se)-1
            for i in se:
                if i >root:
                    pos = se.index(i)
                    break
            left = se[:pos]
            right = se[pos:-1]
            for j in right:
                if j<root:
                    return False
            return check(left) and check(right)

        return check(sequence)

先使用长度为0排除掉空树
而在后续check中就允许有长度为0的情况了
而且长度为0说明直接可行
还有就是长度为2的直接可行！！！！是非常重要的结束条件
其实整个递归树相当于是一个筛子
逐层筛选出合格的或者不合格的
筛不出来的就进入下一轮筛选