剑指 Offer 32 - I. 从上到下打印二叉树 - leetcode 剑指offer系列
发布日期:2021-06-29 07:12:07
浏览次数:3
分类:技术文章
本文共 1583 字,大约阅读时间需要 5 分钟。
题目难度: 中等
今天继续更新剑指 offer 系列, 这道题和接下来两道题很类似, 属于非常经典的 BFS, 这里提供两种实现方案供大家参考
老样子晚上 6 点 45 分准时更新公众号 每日精选算法题, 大家记得关注哦~ 另外在公众号里回复 offer 就能看到剑指 offer 系列当前连载的所有文章了
题目描述
从上到下打印出二叉树的每个节点,同一层的节点按照从左到右的顺序打印。
- 节点总数 <= 1000
题目样例
示例
输入
给定二叉树: [3,9,20,null,null,15,7],
3 / \ 9 20 / \ 15 7
输出
[3,9,20,15,7]
题目思考
- 哪些数据结构可以做到按层输出?
解决方案
思路
- 经典的 BFS 思路, 将当前节点的左右非空子节点追加到队列结尾, 然后继续往后遍历队列, 最终整个队列就是最后的结果
- 由于这里是树, 所以每个节点只可能被加入队列访问一次, 无需额外的 visit 集合
- 另外这道题不需要分开保存每一层的节点, 所以这里不需要记录当前层的长度之类的情况, 可以直接一次循环搞定
- 数据结构方面, 可以采用列表 + 动态的 for 循环(python 3 适用, 其他语言可能不支持遍历过程中更改容器)或者双端队列 + while 循环(所有语言通用, 每次 pop 最左边的元素作为当前节点)
- 下面的代码是个人觉得比较通用的 BFS 模板, 包括列表和双端队列两种方式的实现, 适用于不需要单独处理每一层节点的情况, 供大家参考
复杂度
- 时间复杂度
O(N)
- 每个节点只需要遍历一次
- 空间复杂度
O(N)
- 额外需要一个列表/双端队列
代码
方案 1 - 列表 + for 循环
class Solution: def levelOrder(self, root: TreeNode) -> List[int]: # 方案1: 列表+for循环 if not root: return [] q = [root] for node in q: # 只将非空子节点追加到队列 if node.left: q.append(node.left) if node.right: q.append(node.right) return [x.val for x in q]
方案 2 - 双端队列 + while 循环
import collectionsclass Solution: def levelOrder(self, root: TreeNode) -> List[int]: # 方案2: 双端队列+while循环 if not root: return [] q = collections.deque([root]) res = [] while q: node = q.popleft() res.append(node.val) if node.left: q.append(node.left) if node.right: q.append(node.right) return res
大家可以在下面这些地方找到我~😊
我的公众号: 每日精选算法题, 欢迎大家扫码关注~😊
转载地址:https://blog.csdn.net/zjulyx1993/article/details/107367942 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
关注你微信了!
[***.104.42.241]2024年04月12日 23时36分22秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
RTE 2020实时互联网大会今日开幕 探讨实时互动的场景化创新与技术衍变
2019-04-29
声网发布Agora云市场2.0计划 全球注册应用开发者突破21万
2019-04-29
10个颠覆性创业项目来了!RTE 2020 实时互联网创业挑战赛圆满收官
2019-04-29
用VScode 插件做代码同步演示,原来实时信令控制还能这么玩
2019-04-29
声网Agora 2020 年 Q3 财报
2019-04-29
声网 X 牛客网 200万场视频面试背后的实时互动技术支撑
2019-04-29
声网X智能作业灯 台灯如何成为在线作业辅导新神器?
2019-04-29
RTC 月度小报 11 月 | 开发者社区全新上线、WebRTC 镜像、大会回顾……
2019-04-29
社区「学习周」喊你来打卡
2019-04-29
RTE 大会回顾 | 基于 Web 引擎技术的 Web 内容录制
2019-04-29
CODING DevOps 演讲回顾:声网 Agora SDK 测试最佳实践
2019-04-29
声网合伙人王骅:聊聊企业拥抱全球化 关键是什么?
2019-04-29
冲顶大会、HQ火了,该如何打造一款在线答题App呢?
2019-04-29
教你如何结合WebRTC与TensorFlow实现图像检测
2019-04-29
直播问答瓶颈及技术方案解读
2019-04-29
技术架构解读:直播答题如何组队开黑
2019-04-29
深入浅出,ARCore开发原理
2019-04-29
H5直播答题并不难,看完这篇你也会
2019-04-29
18个实时音视频开发中会用到开源项目
2019-04-29