题解 | #树的子结构#

# 若是二叉搜索树的后序遍历，那么它的后序列表的最后一个可以将列表分为左右两部分
# 分别是小于它的和大于它的
class Solution:
    def VerifySquenceOfBST(self, sequence: List[int]) -> bool:
        # write code here
        length = len(sequence)
        # 由题目定义，空列表返回False
        if length == 0:
            return False
        elif length == 1 or length == 2:
            return True
        midnum = sequence.pop()
        index = -1
        flag = 0
        for ind, val in enumerate(sequence):
            # 根据更大的值确定列表最后元素中间值的所在位置
            # flag用作标记，如果找到大于最后元素的值，在它之后的列表元素都应该大于
            if val > midnum:
                if flag == 0:
                    flag = 1
                    index = ind
            # 输入的列表中，任意元素不想相等
            # elif val < midnum
            else:
                if flag == 1:
                    return False

        if index != -1:
        # 判断一下长度，若递归到列表长度为0，应该返回True
            len1 = len(sequence[:index])
            len2 = len(sequence[index:])
            flag1 = True if len1 == 0 else self.VerifySquenceOfBST(sequence[:index])
            flag2 = True if len2 == 0 else self.VerifySquenceOfBST(sequence[index:])
            subtruth = flag1 and flag2
        else:
            len3 = sequence[:length - 2]
            subtruth = True if len3 == 0 else self.VerifySquenceOfBST(sequence[:length - 2])

        if not subtruth:
            return False
        # 如果排除了错误的情况，就认定可以为正确
        return True