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

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

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

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-14 18:10
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议