二叉树的层次遍历同时涉及到树和队列两种数据结构的操作，因此大厂很喜欢用来作为面试的热身题。作者不少去腾讯的小伙伴，都反映，这种题一定要非常熟练，不然会被直接pass。

1 题目描述

给定一个二叉树，按照层级进行遍历，在每一层中，从左到右进行遍历，并把每一层的元素放到一个数组中。

如下图所示：

2 题目分析

本题中，我们需要一层一层进行树节点的遍历，对此， 我们可以使用广度优先遍历（BFS）来实现。

在遍历一层时，我们同时需要将下一层的节点存储起来，以便可以迭代遍历。这时，用先进先出队列来存储就会非常的方便。

我们的算法遵循如下步骤：

• 1 将root放入队列
• 2 迭代访问队列，直到队列为空
• 3 在每次迭代时，首先确定队列中元素个数，不妨称为levelSize。表示在即将访问的层次中共有levelSize个元素
• 4 依次访问这levelSize个元素，将它们放入一个数组中，同时将它们从队列中移除
• 5 移除每个元素时，讲它的子节点加入队列中
• 6 如果队列非空，则回到3，继续访问下一层次的节点

动画展示：

3 代码实现

from collections import deque


class TreeNode:
  def __init__(self, val):
    self.val = val
    self.left, self.right = None, None


def traverse(root):
  result = []
  if root is None:
    return result

  queue = deque()
  queue.append(root)
  while queue:
    levelSize = len(queue)
    currentLevel = []
    for _ in range(levelSize):
      currentNode = queue.popleft()
      # 将节点添加到数组中
      currentLevel.append(currentNode.val)
      # 将节点的子节点添加到队列中
      if currentNode.left:
        queue.append(currentNode.left)
      if currentNode.right:
        queue.append(currentNode.right)

    result.append(currentLevel)

  return result