二叉树的层平均值 图解题解

这道题到底在问什么

输入

[3,9,20,null,null,15,7]

输出

[3, 14.5, 11]

输入

空树 []

输出

[]

最优解：一步一步想明白

1. 3记住「队列按层展开,每层求和再除以个数」,下面逐帧套它。
2. 4按深度分层先找感觉:同一深度的节点属于同一层。根 48 是第 0 层,孩子 31、70 是第 1 层,再往下 24、36、60、20 是第 2 层。我们要在每一层里把所有值加起来、除以个数得平均。
3. 5本层 1 个节点进入第 0 层,队列里是 [48]。先把这一整层从左到右扫一遍,边扫边把值累进「本层和」、并数清「个数」。
4. 6加 48从队首取出 48(红),把它累加进本层和:0 + 48 = 48,个数变成 1。这是本层最后一个。
5. 748 → 31,7048 加完了。把它的非空孩子 31、70(蓝色)加入下一层,目前下一层攒到了 [31、70]。
6. 8第 0 层取 48第 0 层整层扫完:和是 48、共 1 个,平均 48 ÷ 1 = 48,记进答案。现在各层平均是 [48]。下一层 [31、70] 已就绪,继续。
7. 9本层 2 个节点进入第 1 层,队列里是 [31、70]。先把这一整层从左到右扫一遍,边扫边把值累进「本层和」、并数清「个数」。
8. 10加 31从队首取出 31(红),把它累加进本层和:0 + 31 = 31,个数变成 1。本层还剩 [70] 没加。
9. 1131 → 24,3631 加完了。把它的非空孩子 24、36(蓝色)加入下一层,目前下一层攒到了 [24、36]。
10. 12加 70从队首取出 70(红),把它累加进本层和:31 + 70 = 101,个数变成 2。这是本层最后一个。
11. 1370 → 60,2070 加完了。把它的非空孩子 60、20(蓝色)加入下一层,目前下一层攒到了 [24、36、60、20]。
12. 14第 1 层取 50.5第 1 层整层扫完:和是 101、共 2 个,平均 101 ÷ 2 = 50.5,记进答案。现在各层平均是 [48、50.5]。下一层 [24、36、60、20] 已就绪,继续。
13. 15本层 4 个节点进入第 2 层,队列里是 [24、36、60、20]。先把这一整层从左到右扫一遍,边扫边把值累进「本层和」、并数清「个数」。
14. 16加 24从队首取出 24(红),把它累加进本层和:0 + 24 = 24,个数变成 1。本层还剩 [36、60、20] 没加。
15. 1724 是叶子24 是叶子,没有孩子可加,下一层暂时还是 [空]。
16. 18加 36从队首取出 36(红),把它累加进本层和:24 + 36 = 60,个数变成 2。本层还剩 [60、20] 没加。
17. 1936 是叶子36 是叶子,没有孩子可加,下一层暂时还是 [空]。
18. 20加 60从队首取出 60(红),把它累加进本层和:60 + 60 = 120,个数变成 3。本层还剩 [20] 没加。
19. 2160 是叶子60 是叶子,没有孩子可加,下一层暂时还是 [空]。
20. 22加 20从队首取出 20(红),把它累加进本层和:120 + 20 = 140,个数变成 4。这是本层最后一个。
21. 2320 是叶子20 是叶子,没有孩子可加,下一层暂时还是 [空]。
22. 24第 2 层取 35第 2 层整层扫完:和是 140、共 4 个,平均 140 ÷ 4 = 35,记进答案。现在各层平均是 [48、50.5、35]。没有下一层了,BFS 结束。
23. 25答案 = [48,50.5,35]每一层的平均值依次是 [48、50.5、35]。回头看,就是一遍标准的按层 BFS,每层从左到右把值加起来、再除以个数,一次遍历就出全部答案,时间 O(n)。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import List, Optional
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
        if not root: return []
        q, ans = [root], []
        while q:
            ans.append(sum(n.val for n in q) / len(q))
            q = [c for n in q for c in (n.left, n.right) if c]
        return ans

#include <algorithm>
#include <climits>
#include <functional>
#include <queue>
#include <vector>
using namespace std;
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution { public: vector<double> averageOfLevels(TreeNode* root){ if(!root)return{}; queue<TreeNode*> q; q.push(root); vector<double> ans; while(!q.empty()){ long long sum=0; int sz=q.size(); for(int i=0;i<sz;i++){ auto n=q.front(); q.pop(); sum+=n->val; if(n->left)q.push(n->left); if(n->right)q.push(n->right);} ans.push_back((double)sum/sz);} return ans;} };

import java.util.*;
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; }
}
class Solution { public List<Double> averageOfLevels(TreeNode root){ ArrayList<Double> ans=new ArrayList<>(); if(root==null)return ans; Queue<TreeNode> q=new ArrayDeque<>(); q.offer(root); while(!q.isEmpty()){ long sum=0; int sz=q.size(); for(int i=0;i<sz;i++){ TreeNode n=q.poll(); sum+=n.val; if(n.left!=null)q.offer(n.left); if(n.right!=null)q.offer(n.right);} ans.add((double)sum/sz);} return ans;} }

复杂度

面试官可能追问