当前位置:网站首页>【二叉树】二叉搜索树的后序遍历序列
【二叉树】二叉搜索树的后序遍历序列
2022-08-10 19:06:00 【豪冷啊】
0x00 题目
输入一个整数数组
判断该数组是不是某二叉搜索树的后序
遍历结果
如果是则返回 true
,否则返回 false
假设输入的数组的任意两个数字都互不
相同
0x01 思路
后序遍历的结果是:左,右,中
最后一个是根
节点右
子树的所有节点都 大于
根节点
找到第一个
大于 根节点的 索引
即可区分左右子树
0x02 解法
语言:Swift
树节点:TreeNode
public class TreeNode {
public var val: Int
public var left: TreeNode?
public var right: TreeNode?
public init() { self.val = 0; self.left = nil; self.right = nil; }
public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
self.val = val
self.left = left
self.right = right
}
}
解法:
func verifyPostorder(_ postorder: [Int]) -> Bool {
func verify(_ i: Int, _ j: Int) -> Bool {
// 说明此子树节点数量 ≤ 1 ,无需判断,直接 true
if i >= j { return true }
// 寻找 第一个大于根节点 的节点
// 即左子树 都要小于 要节点
var p = i
while postorder[p] < postorder[j] {
p += 1
}
// 右子树都大于根节点
let m = p
while postorder[p] > postorder[j] {
p += 1
}
// 不再大于时,说明索引应该等于 根节点
let b1 = (p == j)
// 验证左子树
let b2 = verify(i, m-1)
// 验证右子树
let b3 = verify(m, j-1)
return b1 && b2 && b3
}
return verify(0, postorder.count-1)
}
0x03 我的小作品
欢迎体验我的作品之一:小五笔
五笔学习好帮手~App Store
搜索即可~
边栏推荐
- What is the upstream bandwidth and downstream bandwidth of the server?
- [Teach you how to do mini-games] How to lay out the hands of Dou Dizhu?See what the UP master of the 250,000 fan game area has to say
- 西安Biotin-PEG8-IA_IA-PEG8-生物素供应商
- Tf铁蛋白颗粒包载顺铂/奥沙利铂/阿霉素/甲氨蝶呤MTX/紫杉醇PTX等药物
- 今日份bug,点击win10任务栏视窗动态壁纸消失的bug,暂未发现解决方法。
- [Go WebSocket] Your first Go WebSocket server: echo server
- [教你做小游戏] 斗地主的手牌,如何布局?看25万粉游戏区UP主怎么说
- 转铁蛋白修饰蛇床子素长循环脂质体/负载三七皂苷R1的PEG-PLGA纳米粒([email protected] NPs)
- 回老家去?
- laya打包发布apk
猜你喜欢
[Teach you how to do mini-games] How to lay out the hands of Dou Dizhu?See what the UP master of the 250,000 fan game area has to say
- [email protected] NPs纳米酶|碳纳米管负载铂颗粒纳米酶|白血病拮抗多肽修饰的FeOPtPEG复合纳米酶"/>
Pt/CeO2单原子纳米酶|[email protected] NPs纳米酶|碳纳米管负载铂颗粒纳米酶|白血病拮抗多肽修饰的FeOPtPEG复合纳米酶
YOLOv3 SPP源码分析
Redis persistence mechanism
Modern Privacy-Preserving Record Linkage Techniques: An Overview论文总结
ARouter使用自定义注解处理器,自动生成跳转Activity的代码,避免手动填写和管理path
巧用RoaringBitMap处理海量数据内存diff问题
转铁蛋白(TF)修饰紫杉醇(PTX)脂质体(TF-PTX-LP)|转铁蛋白(Tf)修饰姜黄素脂质体
烟雾、空气质量、温湿度…自己徒手做个环境检测设备
电脑为什么会蓝屏的原因
随机推荐
idea汉化教程[通俗易懂]
【深度学习前沿应用】图像风格迁移
【初学必备】3d游戏建模入门基础知识
代理模式的使用总结
Colocate Join :ClickHouse的一种高性能分布式join查询模型
whois information collection & corporate filing information
多功能纳米酶Ag/PANI|柔性衬底纳米ZnO酶|铑片纳米酶|Ag-Rh合金纳米颗粒纳米酶|铱钌合金/氧化铱仿生纳米酶
铁蛋白-AHLL纳米颗粒|人表皮生长因子-铁蛋白重链亚基纳米粒子(EGF-5Cys-FTH1)|铁蛋白颗粒包载氯霉素Chloramphenicol-Ferritin
Keras深度学习实战(17)——使用U-Net架构进行图像分割
803. 区间合并(贪心)左端点、右端点排序均可
“2022零信任神兽方阵”启动调研,欢迎各单位填报信息
从 Delta 2.0 开始聊聊我们需要怎样的数据湖
弘玑Cyclone与风变科技达成战略合作:优势互补聚焦数字化人才培养
FEMRL: A Framework for Large-Scale Privacy-Preserving Linkage of Patients’ Electronic Health Rec论文总结
[Teach you how to make a small game] Write a function with only a few lines of native JS to play sound effects, play BGM, and switch BGM
【无标题】基于Huffman和LZ77的GZIP压缩
pytorch使用Dataloader加载自己的数据集train_X和train_Y
运维面试题(每日一题)
keepalived:故障检测自动修复脚本
opengrok搭建[通俗易懂]