AcWing 46. 二叉搜索树的后序遍历序列    原题链接    简单

作者： 作者的头像   月涌江流 ,  2019-03-20 21:43:41 ,  所有人可见 ,  阅读 1796

1


Python 代码

class Solution:
    def verifySequenceOfBST(self, seq):
        if not seq:
            return True
        i = 0
        while seq[i] < seq[-1]:
            i += 1
        for j in seq[i:-1]:
            if j < seq[-1]:
                return False
        return self.verifySequenceOfBST(seq[:i]) and self.verifySequenceOfBST(seq[i:-1])

3 评论

用户头像
CowRy   2019-05-21 15:04         踩      回复

一开始为空应该返回True

    def verifySequenceOfBST(self, seq):

        def dfs(seq):
            if not seq: return True
            i = 0
            root = seq[-1]
            while seq[i] < root:
                i += 1
            for j in seq[i:-1]:
                if j < root:
                    return False
            return dfs(seq[:i]) and dfs(seq[i:-1])

        if not seq: return False
        return dfs(seq)
用户头像
福如东海   2019-05-03 17:23         踩      回复

写得很清晰

用户头像
月涌江流   2019-05-04 11:28         踩      回复

python的切片还是好用啊