首页 > 编程语言 > 详细

剑指offer-二叉搜索树的后序遍历序列-python

时间:2019-11-27 11:56:40      阅读:66      评论:0      收藏:0      [点我收藏+]

题目描述

输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

递归法:

先判断左子树是否存在

再判断右子树是否存在

然后递归判断左子树右子树是否为二叉树

# -*- coding:utf-8 -*-
class Solution:
    def VerifySquenceOfBST(self, sequence):
        if not sequence:
            return False
        lens = len(sequence)
        root = sequence[-1]
        #左子树
        for i in range(lens):
            if sequence[i]>root:
                break
        for j in range(i,lens):
            if sequence[j]<root:
                return False
        left=True        
        if i>0:
            left = self.VerifySquenceOfBST(sequence[:i])
        right=True
        if i <lens-1:
            right = self.VerifySquenceOfBST(sequence[i:-1])
        return left and right

 

剑指offer-二叉搜索树的后序遍历序列-python

原文:https://www.cnblogs.com/ansang/p/11940771.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!