一、题目分析一起刷题吧
输入：二叉树
输出：二叉树的层次遍历，但是锯齿型（Z之型的层次遍历）输出
难度：中等
标签：树,dfs/bfs
示例 1:
给定二叉树 [3,9,20,null,null,15,7]
3
/
9 20
/
15 7
返回锯齿形层序遍历如下：
[ [3], [20,9], [15,7] ]二、参考代码
这个题是对树的层次遍历的改版，即在层次遍历的基础上加上了 Z之型 的条件。我们先来看下基础版本，即二叉树的层次遍历，对应题目链接：
https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
通过 DFS 或者 BFS 都可以解决这个题目。这里给出参考代码：
from typing import List
from collections import deque
# 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 []
cur_level = 1
q = deque([(root, cur_level)])
result = [[]]
while q:
node, level = q.popleft()
if level != cur_level:
result.append([node.val])
cur_level = level
else:
result[-1].append(node.val)
if node.left:
q.append((node.left, level+1))
if node.right:
q.append((node.right, level+1))
return result
对于树的 DFS 与 BFS（注意这里说的是树，并不一定是二叉树）一定要把代码背下来，面试时是常考的，还有常考的题目有二叉树的左（右）视图（这个题目在很多次面试都遇到过），题目链接如下：
https://leetcode-cn.com/problems/binary-tree-right-side-view/
同样给出我的参考代码：
# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def rightSideView(self, root: TreeNode) -> List[int]:
if not root:
return []
q1 = deque([root])
q2 = deque()
result = []
tmp = []
while q1 or q2:
cur = q1.popleft()
# tmp.append(cur.value)
if(cur.left):
q2.append(cur.left)
if(cur.right):
q2.append(cur.right)
if not q1:
result.append(cur.val)
q1 = q2
q2 = deque()
return result
其实有了上面层次遍历的基础，我们再来做这个题目就很简单了。关键在于层次的奇偶性，当是奇数时，则从左到右，如果是偶数时，则从右到左存储。
就按照上面的思路，我们对层次遍历做下层数的判断就解决了。参考代码如下：
from collections import deque
from typing import List
class Solution:
def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
cur_level = 1
q = deque([(root, cur_level)])
result = []
tmp = []
while q:
node, level = q.popleft()
if level != cur_level:
if cur_level % 2 == 1:
result.append(tmp)
else:
result.append(tmp[::-1])
tmp = []
cur_level = level
tmp.append(node.val)
if node.left:
q.append((node.left, cur_level+1))
if node.right:
q.append((node.right, cur_level+1))
if cur_level % 2 == 1:
result.append(tmp)
else:
result.append(tmp[::-1])
return result
三、附加
对于树的题目，本地测试时，需要构建树的结构，通常输入是一个 list。因此这里给出一些工具方法，可以通过 list 构建一个二叉树，同时也可以输入一个二叉树，打印出 list。
参考代码如下：
from collections import deque
from typing import List
# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def buildTreeNodeByList(list: List[int]):
if not list:
return
root = TreeNode(list[0])
q = deque([root])
i = 0
while i < len(list) and i + 1 < len(list) and i + 2 < len(list) and q:
node = q.popleft()
if list[i+1]:
node.left = TreeNode(list[i+1])
if list[i+2]:
node.right = TreeNode(list[i+2])
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
i += 2
return root
def printTreeNode(root: TreeNode):
# 层次遍历打印
q = deque([root])
result = []
while q:
node = q.popleft()
if not node:
result.append(None)
else:
result.append(node.val)
q.append(node.left)
q.append(node.right)
while not result[-1]:
result.pop(-1)
print(result)
