【Leetcode刷题Python】剑指 Offer 33. 二叉搜索树的后序遍历序列

简介: 本文提供了一种Python算法,用以判断给定整数数组是否为某二叉搜索树的后序遍历结果,通过识别根节点并递归验证左右子树的值是否满足二叉搜索树的性质。

1 题目

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

参考以下这颗二叉搜索树:

     5
    / \
   2   6
  / \
 1   3

示例 1:

输入: [1,6,3,2,5]
输出: false
示例 2:

输入: [1,3,2,6,5]
输出: true

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

2 解析

(1)先找到根节点的右子节点
根节点是后续遍历序列的最后一个值,从后向前遍历序列,找到比根节点小的第一个数就是根节点的右子节点

(2)然后判断右子树的值是否全大于root,左子树的值是否都小于root

(3)然后再递归根节点的左右子树即可

3 python实现

class Solution:
    def verifyPostorder(self, postorder: List[int]) -> bool:

        if not postorder:return True
        root = postorder[-1]
        idx = 0
        for i in range(len(postorder)):
            if postorder[i]>=root:
                idx = i
                break
        left = postorder[:idx]
        right  = postorder[idx:-1]
        # 判断右子树的节点都大于根节点
        for val in right:
            if val<root:
                return False
        # 判断左子树的节点都小于根节点
        for val in left:
            if val>root:
                return False
        return self.verifyPostorder(left) and self.verifyPostorder(right)
目录
相关文章
|
1月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
60 2
|
24天前
|
算法
LeetCode第96题不同的二叉搜索树
文章介绍了LeetCode第96题"不同的二叉搜索树"的解法,利用动态规划的思想和递推公式,通过计算以任意节点为根的不同二叉搜索树的数量,解决了该问题。
LeetCode第96题不同的二叉搜索树
|
24天前
|
算法 Java
LeetCode第94题二叉树的中序遍历
文章介绍了LeetCode第94题"二叉树的中序遍历"的解法,使用递归实现了中序遍历的过程,遵循了"左根右"的遍历顺序,并提供了清晰的Java代码实现。
LeetCode第94题二叉树的中序遍历
|
1月前
|
Python
【Leetcode刷题Python】50. Pow(x, n)
本文介绍了LeetCode第50题"Pow(x, n)"的解法,题目要求实现计算x的n次幂的函数,文章提供了递归分治法的详细解析和Python实现代码。
14 1
|
12天前
|
运维 算法 数据挖掘
5个适合新手练习的Python刷题网站
5个适合新手练习的Python刷题网站
|
1月前
|
算法 Python
【Leetcode刷题Python】73. 矩阵置零
本文介绍了LeetCode第73题的解法,题目要求在给定矩阵中将所有值为0的元素所在的行和列全部置为0,并提供了一种原地算法的Python实现。
16 0
【Leetcode刷题Python】73. 矩阵置零
|
1月前
|
存储 算法 Java
LeetCode经典算法题:二叉树遍历(递归遍历+迭代遍历+层序遍历)以及线索二叉树java详解
LeetCode经典算法题:二叉树遍历(递归遍历+迭代遍历+层序遍历)以及线索二叉树java详解
53 0
|
1月前
|
Python
【Leetcode刷题Python】1467. 两个盒子中球的颜色数相同的概率
本文介绍了LeetCode第50题"Pow(x, n)"的解法,题目要求实现计算x的n次幂的函数,文章提供了递归分治法的详细解析和Python实现代码。
16 0
|
1月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
37 6
|
1月前
|
Python
【Leetcode刷题Python】剑指 Offer 26. 树的子结构
这篇文章提供了解决LeetCode上"剑指Offer 26. 树的子结构"问题的Python代码实现和解析,判断一棵树B是否是另一棵树A的子结构。
33 4
下一篇
DDNS