Algorithm
Problem Name: 637. Average of Levels in Binary Tree
Given the 
root of a binary tree, return the average value of the nodes on each level in the form of an array. Answers within 10-5 of the actual answer will be accepted.
Example 1:
Input: root = [3,9,20,null,null,15,7] Output: [3.00000,14.50000,11.00000] Explanation: The average value of nodes on level 0 is 3, on level 1 is 14.5, and on level 2 is 11. Hence return [3, 14.5, 11].
Example 2:
Input: root = [3,9,20,15,7] Output: [3.00000,14.50000,11.00000]
Constraints:
- The number of nodes in the tree is in the range
[1, 104]. -231 <= Node.val <= 231 - 1
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
vector<double> averageOfLevels(TreeNode* root) {
vector<double>res;
if(!root) return res;
deque < TreeNode*>cur;
dequenext;
cur.push_back(root);
double sum = 0;
int n = 0;
while(!cur.empty()){
TreeNode* p = cur.front();
cur.pop_front();
sum += p->val;
n++;
if(p->left) next.push_back(p->left);
if(p->right) next.push_back(p->right);
if(cur.empty()){
res.push_back(sum / n);
swap(cur, next);
sum = n = 0;
}
}
return res;
}
};
Input
root = [3,9,20,null,null,15,7]
Output
[3.00000,14.50000,11.00000]
#2 Code Example with Java Programming
Code -
Java Programming
class Solution {
public List averageOfLevels(TreeNode root) {
List result = new ArrayList<>();
Queue < TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int size = queue.size();
double total = 0.0;
for (int i = 0; i < size; i++) {
TreeNode removed = queue.remove();
total += removed.val;
if (removed.left != null) {
queue.add(removed.left);
}
if (removed.right != null) {
queue.add(removed.right);
}
}
result.add(total / size);
}
return result;
}
}
Input
root = [3,9,20,null,null,15,7]
Output
[3.00000,14.50000,11.00000]
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const averageOfLevels = function(root) {
const res = [];
layer(res, [root]);
return res.map(el => el.val / el.num);
};
function layer(arr, args) {
const item = {
val: args.reduce((ac, el) => ac + el.val, 0),
num: args.length
};
arr.push(item);
const children = [];
args.forEach(el => {
el.left === null ? null : children.push(el.left);
el.right === null ? null : children.push(el.right);
});
if (children.length) {
layer(arr, children);
}
}
Input
root = [3,9,20,15,7]
Output
[3.00000,14.50000,11.00000]
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def averageOfLevels(self, root):
"""
:type root: TreeNode
:rtype: List[float]
"""
from collections import deque
q, target, avg = deque([root]), root, [float(root.val)]
while q:
node=q.popleft()
if node.left: q.append(node.left)
if node.right: q.append(node.right)
if q and node==target:
target, sm = q[-1], 0
for item in q: sm+=item.val
avg.append(sm/len(q))
return avg
Input
root = [3,9,20,15,7]
Output
[3.00000,14.50000,11.00000]
#5 Code Example with C# Programming
Code -
C# Programming
using System.Collections.Generic;
namespace LeetCode
{
public class _0637_AverageOfLevelsInBinaryTree
{
public IList < double> AverageOfLevels(TreeNode root)
{
var result = new List();
if (root == null) return result;
var queue = new Queue < TreeNode>();
queue.Enqueue(root);
while (queue.Count > 0)
{
var levelCount = queue.Count;
double sum = 0.0;
for (int i = 0; i < levelCount; i++)
{
var node = queue.Dequeue();
sum += node.val;
if (node.left != null) queue.Enqueue(node.left);
if (node.right != null) queue.Enqueue(node.right);
}
result.Add(sum / levelCount);
}
return result;
}
}
}
Input
root = [3,9,20,null,null,15,7]
Output
[3.00000,14.50000,11.00000]