【Leetcode刷题Python】103. 二叉树的锯齿形层序遍历
2023-09-14 09:13:02 时间
1 题目
给你二叉树的根节点 root ,返回其节点值的 锯齿形层序遍历 。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。
示例 1:
输入:root = [3,9,20,null,null,15,7]
输出:[[3],[20,9],[15,7]]
示例 2:
输入:root = [1]
输出:[[1]]
示例 3:
输入:root = []
输出:[]
2 解析
为了满足题目要求的返回值为「先从左往右,再从右往左」交替输出的锯齿形,我们可以利用「双端队列」的数据结构来维护当前层节点值输出的顺序。
双端队列是一个可以在队列任意一端插入元素的队列。在广度优先搜索遍历当前层节点拓展下一层节点的时候我们仍然从左往右按顺序拓展,但是对当前层节点的存储我们维护一个变量 flag记录是从左至右还是从右至左的:
-
如果从左至右,我们每次将被遍历到的元素插入至双端队列的末尾。
-
如果从右至左,我们每次将被遍历到的元素插入至双端队列的头部。
当遍历结束的时候我们就得到了答案数组。
3 Python实现
def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
res = []
q =deque([root])
flag = True
while q and q[0]:
n = len(q)
tmp = []
for _ in range(n):
node = q.popleft()
tmp.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
if flag:
res.append(tmp)
else:
tmp.reverse()
res.append(tmp)
flag = not flag
return res
相关文章
- Python每日一练(20230419)
- python程序员都在用到5个酷毙的Python工具
- Python编程语言学习:python中浅复制/深复制(或浅拷贝/深拷贝)的简介、案例应用注意事项之详细攻略
- Python之tkinter:动态演示调用python库的tkinter带你进入GUI世界(Entry/Entry的Command)
- Python语言学习之双下划线那些事:python和双下划线使用方法之详细攻略
- python --> Python初阶 --> 基础语法 --> 条件和分支
- 已解决2.Set PROTOCOL_BUFFERS_PYTHON_IMPLEMENTATION=python (but this will use pure-Python parsing and wi
- 【LeetCode Python实现】300. 最长递增子序列(中等)动态规划
- 【华为OD机试 2023】 过滤组合字符串(C++ Java JavaScript Python)
- Python编程:查看python语法中的关键字keyword
- python 手动遍历迭代器
- python 多进程并发demo
- 写网络爬虫天然就是择Python而用 python 网络爬虫3
- 【Leetcode刷题Python】102. 二叉树的层序遍历
- 【Leetcode刷题Python】145. 二叉树的后序遍历
- 【Leetcode刷题Python】155. 最小栈
- 【Leetcode刷题Python】111. 二叉树的最小深度
- 【Leetcode刷题Python】297. 二叉树的序列化与反序列化
- 【Leetcode刷题Python】105. 从前序与中序遍历序列构造二叉树
- 【Leetcode刷题Python】剑指 Offer 03. 数组中重复的数字
- Python学习笔记之简易计算器
- Python 性能测试 Locust 实例