【Leetcode刷题Python】剑指 Offer 33. 二叉搜索树的后序遍历序列
2023-09-14 09:13:02 时间
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)
相关文章
- 量化投资策略:常见的几种Python回测框架(库)
- Python发送企业微信群机器人消息
- Python 刷Leetcode题库,顺带学英语单词(34)
- Python 刷Leetcode题库,顺带学英语单词(27)
- Atitit python3.0 3.3 3.5 3.6 新特性 Python2.7新特性1Python 3_x 新特性1python3.4新特性1python3.5新特性1值得关注的新特性1Python3.6新特性2 Python2.7新特性Python 2.7的新特性 - 牛皮糖NewPtone - 博客园.html Python 3_x 新特性及10大变化_python_脚本之家.htm
- Python编程语言学习:包导入和模块搜索路径(包路径)简介、使用方法(python系统环境路径的查询与添加)之详细攻略
- Python之ffmpeg:利用python编程基于ffmpeg将m4a格式音频文件转为mp3格式文件
- Python编程语言学习:python的列表的特殊应用之一行命令实现if判断中的两类判断
- 成功解决Python中出现的ValueError: not enough values to unpack (expected 2, got 1)的问题
- 已解决2.Set PROTOCOL_BUFFERS_PYTHON_IMPLEMENTATION=python (but this will use pure-Python parsing and wi
- 〖Python自动化办公篇⑦〗- word文件自动化 - 实操之筛选简历
- 【LeetCode Python实现】356. 直线镜像(中等)
- 【Leetcode刷题Python】231. 2 的幂
- 【Leetcode刷题Python】35. 搜索插入位置
- 【Leetcode刷题Python】718. 最长重复子数组
- 【Leetcode刷题Python】96. 不同的二叉搜索树
- Python可视化数据分析01、python环境搭建