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

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

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

全部评论

相关推荐

06-08 22:25
门头沟学院 Java
从零开始的转码生活:这hr不会打开手机不分青红皂白给所有人群发这句话,过一会再给所有人再发一遍,这肯定会有重复的,不管,再过一会再发一遍
点赞 评论 收藏
分享
小浪_Coding:找硬件测试,也可兼顾软测欧, 简历还可以的 ,注意排版,项目写的有条理一点, 然后个人技能多加点, 润色好简历之后就开始沟通海投了,深圳,东莞这边做硬件相关的公司还不少, 医疗类,仪器类的都可以尝试
点赞 评论 收藏
分享
07-02 13:50
闽江学院 Java
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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