请实现一个函数按照之字形顺序打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右到左的顺序打印,第三行再按照从左到右的顺序打印,其他行以此类推。
例如:
给定二叉树: [3,9,20,null,null,15,7]
,
3
/ \
9 20
/ \
15 7
返回其层次遍历结果:
[
[3],
[20,9],
[15,7]
]
在剑指 Offer 32 - II. 从上到下打印二叉树 II的基础上,可以根据层数的奇偶性来判断每层的数据是按照从左到右还是从右到左的排列,上代码
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
result = []
if root:
queue = collections.deque()
queue.append(root)
flag = False
while queue:
sample = []
for _ in range(len(queue)):
node = queue.popleft()
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
sample.append(node.val)
if not flag:
result.append(sample)
else:
sample.reverse()
result.append(sample)
flag = False if flag else True
return result
学习一下大神的解法
解题思路:
面试题32 - I. 从上到下打印二叉树 主要考察 树的按层打印 ;
面试题32 - II. 从上到下打印二叉树 II 额外要求 每一层打印到一行 ;
本题额外要求 打印顺序交替变化(建议按顺序做此三道题)
方法一:层序遍历 + 双端队列
- 利用双端队列的两端皆可添加元素的特性,设打印列表(双端队列)
tmp
,并规定:- 奇数层 则添加至
tmp
尾部 , - 偶数层 则添加至
tmp
头部 。
- 奇数层 则添加至
算法流程:
-
特例处理: 当树的根节点为空,则直接返回空列表
[]
; -
初始化: 打印结果空列表
res
,包含根节点的双端队列deque
; -
BFS 循环: 当
deque
为空时跳出;- 新建列表
tmp
,用于临时存储当前层打印结果; -
当前层打印循环: 循环次数为当前层节点数(即
deque
长度);-
出队: 队首元素出队,记为
node
; -
打印: 若为奇数层,将
node.val
添加至tmp
尾部;否则,添加至tmp
头部; -
添加子节点: 若
node
的左(右)子节点不为空,则加入deque
;
-
出队: 队首元素出队,记为
- 将当前层结果
tmp
转化为list
并添加入res
;
- 新建列表
-
返回值: 返回打印结果列表
res
即可;
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root: return []
res, deque = [], collections.deque([root])
while deque:
tmp = collections.deque()
for _ in range(len(deque)):
node = deque.popleft()
if len(res) % 2: tmp.appendleft(node.val) # 偶数层 -> 队列头部
else: tmp.append(node.val) # 奇数层 -> 队列尾部
if node.left: deque.append(node.left)
if node.right: deque.append(node.right)
res.append(list(tmp))
return res