029 · Average of Levels in Binary Tree

algorithm
Published

June 5, 2026

My First Thoughts

这道题要的是每一层的平均数，所以核心从一开始就很清楚：我得有办法把”同一层的节点”凑到一起算。

第一个本能的想法是从父子关系入手。比如写一个 meanSubnode(node)，传入一个节点，算出它左右孩子的均值：都不存在返回 0，只有一个就用那个，两个都在就求平均。这样第 1 层就是 meanSubnode(root)，第 2 层就是 meanSubnode(root.left) 和 meanSubnode(root.right)……

# 想法（最后会发现走不通）
def meanSubnode(node):
    if node.left is None and node.right is None:
        return 0
    ...

方向上有一点是对的：要按层处理，不能一个节点一个节点乱走。但”用父子关系凑层”这条路本身有问题。

Why That Is Not Enough

问题在于：“层”和”父子”不是一回事。

看这棵树：

      3
     / \
    9  20
   / \    \
  15  7    8

第 2 层是 [15, 7, 8]，要一起算 (15 + 7 + 8) / 3。但这三个节点的父节点并不一样：15、7 是 9 的孩子，8 是 20 的孩子。

如果按”每个父节点算自己孩子的均值”去拆，就会把这一层拆成 [15, 7] 和 [8] 两组，分别落在 meanSubnode(9) 和 meanSubnode(20) 里，再也拼不回同一层。所以 meanSubnode(root.left) + meanSubnode(root.right) 这种写法注定不对。

转念的关键是：

既然靠父子关系凑不出一整层，那就别管父子关系，直接按”距离根的层数”分组。

而要”一层一层、整层整层地处理”，递归（DFS）反而别扭，用队列做 BFS（层序遍历）最自然。

Final Idea

核心技巧只有一个：

进入某一层之前，先记下队列里现在有多少个节点——这个数量就是这一层的节点数。

整个流程像排队买票，先进先出（FIFO）。一开始队列里只放 root，然后反复做：

当队列非空：
    n = 当前队列长度        ← 这就是"这一层有几个节点"
    total = 0
    重复 n 次：             ← 只处理这一层的 n 个，不会串到下一层
        弹出一个节点
        total += 它的值
        把它非空的左右孩子塞进队尾   ← 在为"下一层"攒人
    这一层均值 = total / n，记进答案

为什么这样”分层”是自动发生的、不需要额外判断？靠两件事配合：

  1. 塞的时机：只在”处理某个节点”时才把它的孩子塞进队尾。所以第 N 层全部处理完时，它们的孩子（也就是第 N+1 层的全部）刚好都进了队尾，不多不少。
  2. 取的数量：每轮开始先量一次 n = len(队列)，然后只取 n 个。这 n 个就是完整的一层；取完之后下一层早已在队尾排好，但这一轮碰都不碰。

先进先出保证了上一层先被处理、上一层的孩子按顺序排在后面，n 再把它们一刀切开。所以”谁和谁同层”不用你判断，队列的进出顺序天然分好了。

Why It Works

跟着上面那棵树走一遍队列，就很清楚了（[ ] 表示队列里排着谁）：

开始，只放 root：

队列: [3]

第一轮，进轮前队列有 1 个 → 第 0 层就 1 个。弹出 3 累加，把孩子 9、20 塞队尾：

队列: [9, 20]    →  第 0 层均值 3 / 1 = 3

剩下的 [9, 20] 正好就是第 1 层的全部。

第二轮，进轮前队列有 2 个 → 第 1 层 2 个。弹 9（塞 15、7），弹 20（塞 8）：

队列: [15, 7, 8]  →  第 1 层均值 (9 + 20) / 2 = 14.5

剩下的 [15, 7, 8] 又正好是第 2 层的全部。

第三轮，3 个，全部弹出累加，它们没有孩子：

队列: []          →  第 2 层均值 (15 + 7 + 8) / 3

队列空，结束。每一轮处理的都恰好是完整的一层，所以每层均值都算对了。

Code

from collections import deque

def averageOfLevels(root):
    result = []
    queue = deque([root])

    while queue:
        n = len(queue)          # 进层前的队列长度 = 这一层的节点数
        total = 0

        for _ in range(n):      # 只处理这一层的 n 个节点
            node = queue.popleft()
            total += node.val

            if node.left:
                queue.append(node.left)   # 孩子塞队尾
            if node.right:
                queue.append(node.right)

        result.append(total / n)

    return result

这里用 deque 做队列：popleft() 从头部取节点，append(...) 往尾部塞孩子，先进先出。和普通列表的 pop(0) 不同，popleft() 是 \(O(1)\)，所以整棵树每个节点只会被常数时间地入队、出队一次。

题目保证至少有 1 个节点，所以 root 不会是 None，第一轮 n 也不会是 0，不用担心除零。

Complexity

Time \(O(n)\) - 每个节点恰好入队、出队各一次
Space \(O(w)\) - 队列里最多同时装下一整层，w 是树的最大宽度，最坏情况可到 \(O(n)\)

Takeaway

“按层处理”的题，别想着用父子关系把一层凑出来——同一层的节点父节点可能不同，凑不齐。改用队列做 BFS：每轮开始先量一次队列长度，那就是这一层的节点数，只取这么多个，处理它们时顺手把孩子塞进队尾给下一层。分层不是靠判断，而是靠”先进先出 + 每轮按当前长度切一刀”自动完成的。

← Quiz