13.3 层次遍历

# 13.3 层次遍历

我们可以使用广度优先搜索进行层次遍历。注意，不需要使用两个队列来分别存储当前层的节点和下一层的节点，因为在开始遍历一层的节点时，当前队列中的节点数就是当前层的节点数，只要控制遍历这么多节点数，就能保证这次遍历的都是当前层的节点。

## [637. Average of Levels in Binary Tree](https://leetcode.com/problems/average-of-levels-in-binary-tree/)

### 题目描述

给定一个二叉树，求每一层的节点值的平均数。

### 输入输出样例

输入是一个二叉树，输出是一个一维数组，表示每层节点值的平均数。

```
Input:
    3
   / \
  9  20
     / \
    15  7
Output: [3, 14.5, 11]
```

### 题解

利用广度优先搜索，我们可以很方便地求取每层的平均值。

```py
class Solution:
    def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
        level_avg = []
        if not root:
            return level_avg
        q = collections.deque()
        q.append(root)
        while q:
            count = len(q)
            level_sum = 0
            for _ in range(count):
                node = q.popleft()
                level_sum += node.val
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            level_avg.append(level_sum/ count)
            count = len(q)
        return level_avg
```