剑指 Offer 32 - III. 从上到下打印二叉树 III - leetcode 剑指offer系列
发布日期:2021-06-29 07:12:08
浏览次数:3
分类:技术文章
本文共 1406 字,大约阅读时间需要 4 分钟。
题目难度: 中等
今天继续更新剑指 offer 系列, 这道题相比昨天那道题多了个每层打印方向不同的需求, 聪明的你想到应该如何实现了吗?
老样子晚上 6 点 45 分准时更新公众号 每日精选算法题, 大家记得关注哦~ 另外在公众号里回复 offer 就能看到剑指 offer 系列当前连载的所有文章了
题目描述
请实现一个函数按照之字形顺序打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右到左的顺序打印,第三行再按照从左到右的顺序打印,其他行以此类推。
- 节点总数 <= 1000
题目样例
示例
输入
给定二叉树: [3,9,20,null,null,15,7],
3 / \ 9 20 / \ 15 7
输出
[ [3], [20,9], [15,7]]
题目思考
- 可以继续利用昨天的方案吗, 不行的话需要进行哪些改动?
解决方案
思路
- 回顾昨天那道题
剑指 Offer 32 - II. 从上到下打印二叉树 II - leetcode 剑指offer系列
, 我们是单独打印每一层的节点, 只不过都是从左到右的方向 - 针对这道题, 我们可以额外维护一个变量, 记录当前方向, 每次到下一层时就调换方向即可
- 也就是说, 只需要对昨天题目的代码稍加改动就能搞定, 所以熟练掌握前面两种 BFS 的模板是很有必要的, 很多问题都能在它们基础上解决
复杂度
- 时间复杂度
O(N)
- 每个节点只需要遍历一次
- 空间复杂度
O(N)
- 额外需要一个队列
代码
class Solution: def levelOrder(self, root: TreeNode) -> List[List[int]]: res = [] if not root: return res q = [root] # 初始从左到右遍历 fromleft = True while q: curlen = len(q) cur = [] for node in q[:curlen]: cur.append(node.val) if node.left: q.append(node.left) if node.right: q.append(node.right) if fromleft: res.append(cur) else: # 从右向左的话只需要将该层的值翻转加入结果中即可 res.append(cur[::-1]) # 每一层结束后都调转方向 fromleft = not fromleft q = q[curlen:] return res
大家可以在下面这些地方找到我~😊
我的公众号: 每日精选算法题, 欢迎大家扫码关注~😊
转载地址:https://blog.csdn.net/zjulyx1993/article/details/107414683 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
留言是一种美德,欢迎回访!
[***.207.175.100]2024年04月19日 18时34分29秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
元宵节电商促销首页设计PSD分层模板
2019-04-29
APP设计灵感|高颜值时钟页面!让每一秒都过得有意义
2019-04-29
值得电商美工借鉴的购物APP页面设计,让人无法自拔
2019-04-29
电商产品页多种出彩表现设计手法!
2019-04-29
分布式与集成
2019-04-29
C#SUM函数改变数据精度问题
2019-04-29
机器翻译/注意力机制
2019-04-29
Transformer介绍
2019-04-29
SpringMVC异常处理之第三种:ExceptionHandler注解
2019-04-29
如何通过Eclipse来创建SpringBoot项目?
2019-04-29
Spring中 JavaConfig和常见注解
2019-04-29
SpringBoot启动类注解简要介绍
2019-04-29
Spring Boot扩展启动行为-改变启动Banner
2019-04-29
如何通过设置setting加快Maven 及更新SpringBoot项目的速度
2019-04-29
如何设置Spring Boot热部署
2019-04-29
Spring Boot整合Web开发-JSON
2019-04-29
Spring Boot整合Web开发-如何集合模板Thymeleaf?
2019-04-29
Spring Boot整合Web开发-freemarker
2019-04-29
Spring Boot整合Web开发之如何集成JSP
2019-04-29
全局异常处理之自定义全局错误页面、404及500错误页面
2019-04-29