Description

637. Average of Levels in Binary Tree

Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array.

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

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]. Note: The range of node’s value is in the range of 32-bit signed integer.

## DFS O(n) solution

ToDo: re-think the self-defined tuple class since it is frequently used in Java.

``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {

public List<Double> averageOfLevels(TreeNode root) {
List<Tuple> levels = new ArrayList<>();
dfs(root, 0, levels);
List<Double> ret = Arrays.asList(new Double[levels.size()]);
for (int i=0; i<levels.size(); i++) {
Tuple t = levels.get(i);
ret.set(i, t.sum/t.count);
}
return ret;
}

private void dfs(TreeNode root, int level, List<Tuple> levels) {
if (root==null) return;
if (level==levels.size()) {
} else {
Tuple t = levels.get(level);
}
dfs(root.left, level+1, levels);
dfs(root.right, level+1, levels);
}
}

class Tuple {
public Double sum;
public int count;
public Tuple(Double initVal) {
sum = initVal;
count = 1;
} Runtime: around 9ms