LeetCode 637: Average of Levels in Binary Tree (Level Sum / BFS)
LeetCode 637Binary TreeBFSToday we solve LeetCode 637 - Average of Levels in Binary Tree.
Source: https://leetcode.com/problems/average-of-levels-in-binary-tree/
English
Problem Summary
Given the root of a binary tree, return the average value of nodes on each depth level, from top to bottom.
Key Insight
Traverse the tree level by level. For each level, compute sum and divide by the number of nodes in that level.
Algorithm
- Use a queue for BFS.
- For each round, read current queue size as the level width.
- Pop exactly that many nodes, accumulate level sum, and push children.
- Append sum / width to result.
Complexity Analysis
Let n be node count.
Time: O(n).
Space: O(w), where w is max level width (worst-case O(n)).
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public List<Double> averageOfLevels(TreeNode root) {
List<Double> ans = new ArrayList<>();
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
int size = q.size();
double sum = 0.0;
for (int i = 0; i < size; i++) {
TreeNode node = q.poll();
sum += node.val;
if (node.left != null) q.offer(node.left);
if (node.right != null) q.offer(node.right);
}
ans.add(sum / size);
}
return ans;
}
}func averageOfLevels(root *TreeNode) []float64 {
q := []*TreeNode{root}
ans := make([]float64, 0)
for len(q) > 0 {
size := len(q)
sum := 0.0
for i := 0; i < size; i++ {
node := q[0]
q = q[1:]
sum += float64(node.Val)
if node.Left != nil {
q = append(q, node.Left)
}
if node.Right != nil {
q = append(q, node.Right)
}
}
ans = append(ans, sum/float64(size))
}
return ans
}class Solution {
public:
vector<double> averageOfLevels(TreeNode* root) {
vector<double> ans;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int size = q.size();
double sum = 0;
for (int i = 0; i < size; i++) {
TreeNode* node = q.front();
q.pop();
sum += node->val;
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
ans.push_back(sum / size);
}
return ans;
}
};from collections import deque
class Solution:
def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
q = deque([root])
ans = []
while q:
size = len(q)
level_sum = 0
for _ in range(size):
node = q.popleft()
level_sum += node.val
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
ans.append(level_sum / size)
return ansvar averageOfLevels = function(root) {
const q = [root];
const ans = [];
while (q.length > 0) {
const size = q.length;
let sum = 0;
for (let i = 0; i < size; i++) {
const node = q.shift();
sum += node.val;
if (node.left) q.push(node.left);
if (node.right) q.push(node.right);
}
ans.push(sum / size);
}
return ans;
};中文
题目概述
给定二叉树根节点，按层计算每一层节点值的平均数，并返回这些平均值。
核心思路
使用层序遍历（BFS）。每次固定处理当前层节点数，累计该层总和后除以节点数量即可得到层平均值。
算法步骤
- 用队列初始化为根节点。
- 每轮记录当前队列长度作为本层节点数。
- 弹出本层全部节点并累加 sum，同时把左右子节点入队。
- 将 sum / 本层节点数 加入答案。
复杂度分析
设节点总数为 n。
时间复杂度：O(n)。
空间复杂度：O(w)，其中 w 是最大层宽，最坏为 O(n)。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public List<Double> averageOfLevels(TreeNode root) {
List<Double> ans = new ArrayList<>();
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
int size = q.size();
double sum = 0.0;
for (int i = 0; i < size; i++) {
TreeNode node = q.poll();
sum += node.val;
if (node.left != null) q.offer(node.left);
if (node.right != null) q.offer(node.right);
}
ans.add(sum / size);
}
return ans;
}
}func averageOfLevels(root *TreeNode) []float64 {
q := []*TreeNode{root}
ans := make([]float64, 0)
for len(q) > 0 {
size := len(q)
sum := 0.0
for i := 0; i < size; i++ {
node := q[0]
q = q[1:]
sum += float64(node.Val)
if node.Left != nil {
q = append(q, node.Left)
}
if node.Right != nil {
q = append(q, node.Right)
}
}
ans = append(ans, sum/float64(size))
}
return ans
}class Solution {
public:
vector<double> averageOfLevels(TreeNode* root) {
vector<double> ans;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int size = q.size();
double sum = 0;
for (int i = 0; i < size; i++) {
TreeNode* node = q.front();
q.pop();
sum += node->val;
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
ans.push_back(sum / size);
}
return ans;
}
};from collections import deque
class Solution:
def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
q = deque([root])
ans = []
while q:
size = len(q)
level_sum = 0
for _ in range(size):
node = q.popleft()
level_sum += node.val
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
ans.append(level_sum / size)
return ansvar averageOfLevels = function(root) {
const q = [root];
const ans = [];
while (q.length > 0) {
const size = q.length;
let sum = 0;
for (let i = 0; i < size; i++) {
const node = q.shift();
sum += node.val;
if (node.left) q.push(node.left);
if (node.right) q.push(node.right);
}
ans.push(sum / size);
}
return ans;
};
Comments