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()) {
            levels.add(new Tuple((Double)((double)root.val)));
        } else {
            Tuple t = levels.get(level);
            t.addVal((Double)((double)root.val));
        }
        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;
    }
    
    protected void addVal(Double val) {
        sum += val;
        count++;
    }
    
}                            

imgRuntime: around 9ms