剑指 是否为二叉搜索树

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

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

使用递归方法,先找到大于根节点的节点,该节点为左右子树分界点,然后分别去判断左右子树是否为二叉搜索树。注意数组为空时,不是二叉搜索树。

# -*- coding:utf-8 -*-
class Solution:
    def JudgeSquence(self,sequence):
        if len(sequence)<=1:
            return True
        root =sequence[-1]

        for i in range(len(sequence)):
            if sequence[i]>root:
                break
#         if sequence[i]==root:
#             return True


        for j in range(i,len(sequence)-1):
            if sequence[j]<root:
                print(sequence[j])
                return False
        if i==0:
            return self.VerifySquenceOfBST(sequence[i:-1])
        if i==len(sequence)-1:
            return self.VerifySquenceOfBST(sequence[:i])
        return self.VerifySquenceOfBST(sequence[:i]) and self.VerifySquenceOfBST(sequence[i:-1])
    def VerifySquenceOfBST(self, sequence):
        # write code here

        if len(sequence)==0:
            return False
        return self.JudgeSquence(sequence)
全部评论

相关推荐

05-01 22:41
中南大学 Java
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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