剑指 是否为二叉搜索树

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

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)

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

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议