剑指 Offer 32 - III. 从上到下打印二叉树 III
说明
请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
示例
给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层次遍历结果：
[
[3],
[20,9],
[15,7]
]
题解思路
1、在从上到下打印二叉树 II的前提下，将偶数层的节点逆向存入列表即可 2、使用双端队列，偶数层从左端添加节点，奇数层从右端添加
相关题目
从上到下打印二叉树 从上到下打印二叉树 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]]:
if not root:
return []
queue = collections.deque()
queue.append(root)
ans = []
k = 0
while queue:
n = len(queue)
tmp = []
for i in range(n):
node = queue.popleft()
tmp.append(node.val)
left, right = node.left, node.right
if left:
queue.append(left)
if right:
queue.append(right)
if k == 0:
ans.append(tmp)
else:
ans.append(tmp[::-1]) // 如果是偶数层，倒序添加到ans中
k = 1 if k == 0 else 0
return ans
方法二：
# 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]]:
if not root:
return []
queue = collections.deque()
queue.append(root)
ans = []
k = 0
while queue:
n = len(queue)
tmp = collections.deque()
for i in range(n):
node = queue.popleft()
if k == 0:
tmp.append(node.val) // 如果是奇数层，从右边添加节点
else:
tmp.appendleft(node.val) // 如果是偶数层，从左边添加节点
left, right = node.left, node.right
if left:
queue.append(left)
if right:
queue.append(right)
ans.append(list(tmp))
k = 1 if k == 0 else 0
return ans
