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

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

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

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的直接可行!!!!是非常重要的结束条件
其实整个递归树相当于是一个筛子
逐层筛选出合格的或者不合格的
筛不出来的就进入下一轮筛选

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-09 12:05
点赞 评论 收藏
分享
05-29 09:02
门头沟学院 Java
点赞 评论 收藏
分享
人力小鱼姐:实习经历没有什么含金量,咖啡店员迎宾这种就别写了,其他两段包装一下 想找人力相关的话,总结一下个人优势,结合校园经历里有相关性的部分,加一段自我评价
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务