13.3 层次遍历

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

637. Average of Levels in Binary Tree

题目描述

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

输入输出样例

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

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

题解

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

C++

vector<double> averageOfLevels(TreeNode* root) {
    vector<double> level_avg;
    if (root == nullptr) {
        return level_avg;
    }
    queue<TreeNode*> q;
    q.push(root);
    int count = q.size();
    while (count > 0) {
        double level_sum = 0;
        for (int i = 0; i < count; ++i) {
            TreeNode* node = q.front();
            q.pop();
            level_sum += node->val;
            if (node->left != nullptr) {
                q.push(node->left);
            }
            if (node->right != nullptr) {
                q.push(node->right);
            }
        }
        level_avg.push_back(level_sum / count);
        count = q.size();
    }
    return level_avg;
}

Python

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