判断某数组是不是二叉树的后序遍历序列 python递归与非递归解法

一时失言乱红尘 2022-05-14 11:50 90阅读 0赞

# python 递归 #

class Solution:
        def VerifySquenceOfBST(self, sequence):
            # write code here
            if len(sequence) <= 0 or sequence == None:
                return False
            length = len(sequence)
            root = sequence[-1]
            i, j = 0, 0
    
            # i 的范围是[0, length - 1]
            for i in range(length):
                if sequence[i] > root:
                    break
    
            # j的范围是[i, length - 1]
            for j in range(i, length):
                if sequence[j] < root:
                    return False
    
            left = True
            if i > 0:
                left = self.VerifySquenceOfBST(sequence[:i])
    
            right = True
            if j < length - 1:
                right = self.VerifySquenceOfBST(sequence[i:-1])
    
            return left and right

# python 非递归 #

class Solution1:
        def VerifySquenceOfBST(self, sequence):
            # write code here
            if len(sequence) == 0:
                return False
            length = len(sequence) - 1
            i = 0
            while length != 0:
                while sequence[i] < sequence[length]:
                    i += 1
                while sequence[i] > sequence[length]:
                    i += 1
                if i < length:
                    return False
                length -= 1
                i = 0
            return True

发表评论取消回复

表情：

评论列表（有 0 条评论，90人围观）

还没有评论，来说两句吧...

相关阅读

相关二叉树后序遍历(非递归)

叉树的递归遍历算法就不用说了；在非递归算法中，后序遍历难度大，很多书上只给出思想或者几段无法直接调试的代码，甚至有些书上是错的，当时我在研究的过程中，就是按着书上错误的代...

深藏阁楼爱情的钟/ 2024年04月17日 22:41/ 0 赞/ 129 阅读

相关二叉树层次建树，前序（递归与非递归）遍历--中序遍历（递归与非递归）-后序遍历-层次遍历

创建一个二叉树创建项目为创建C++项目 1.导包开始前需要写一些导包 define _CRT_SECURE_NO_WARNINGS incl

忘是亡心i/ 2023年09月29日 11:26/ 0 赞/ 105 阅读

相关二叉树后序遍历（递归+非递归）Java

目录一、结构二、遍历二叉树 1.后序遍历（递归）代码图解 2.后序遍历（非递归）

我不是女神ヾ/ 2023年05月31日 12:21/ 0 赞/ 89 阅读

相关二叉树递归遍历与非递归遍历

二叉树递归遍历与非递归遍历 -------------------- 二叉树递归遍历与非递归遍历引言递归式遍历

ゝ一世哀愁。/ 2022年08月02日 14:43/ 0 赞/ 365 阅读

相关二叉树后序遍历 -- 递归和非递归实现

/实现二叉树后序遍历 -- 采用递归和非递归方法经调试可直接运行源码如下： / include <stdio.h> incl

刺骨的言语ヽ痛彻心扉/ 2022年07月28日 08:59/ 0 赞/ 229 阅读

相关二叉树的后序遍历（递归和非递归）

对于二叉树的后序遍历，最常用的就是递归，代码清晰，如下： ArrayList<Integer> list = new ArrayList<>(); p

川长思鸟来/ 2022年06月06日 01:12/ 0 赞/ 323 阅读

相关判断某数组是不是二叉树的前序遍历序列 python递归

code class Solution: def VerifySquenceOfBST(self, sequence):

素颜马尾好姑娘i/ 2022年05月14日 11:55/ 0 赞/ 91 阅读

相关判断某数组是不是二叉树的后序遍历序列 python递归与非递归解法

python 递归 class Solution: def VerifySquenceOfBST(self, sequence):

一时失言乱红尘/ 2022年05月14日 11:50/ 0 赞/ 91 阅读

相关二叉树的后序遍历（递归与非递归）

二叉树后序遍历介绍了二叉树的先序以及中序遍历，那么我简单的再给大家介绍了一下二叉树的后序遍历。请看大屏幕。。。。 ![在这里插入图片描述][watermark

ゝ一世哀愁。/ 2022年04月24日 07:54/ 0 赞/ 269 阅读

相关二叉树的中序遍历（递归与非递归）

二叉树中序遍历上篇我简单的给大家介绍了一下二叉树的先序遍历，那么这次我就给大家介绍一下二叉树的中序遍历请看大屏幕。。。。 ![在这里插入图片描述][water

水深无声/ 2022年04月24日 07:54/ 0 赞/ 235 阅读