题解 | #树的子结构#

二叉搜索树的后序遍历序列

http://www.nowcoder.com/practice/a861533d45854474ac791d90e447bafd

# 若是二叉搜索树的后序遍历,那么它的后序列表的最后一个可以将列表分为左右两部分
# 分别是小于它的和大于它的
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
全部评论

相关推荐

浪潮 通信信息 20k
点赞 评论 收藏
转发
1 收藏 评论
分享
牛客网
牛客企业服务