637. Average of Levels in Binary Tree

Leetcode 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.

分析

这道题目非常显然的可以用广度优先搜索。搜索每一层，然后计算该层的平均值。

public List<Double> averageOfLevels(TreeNode root) {
    List<Double> average = new ArrayList<>();
    if (root == null) return average;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.off(root);
    while (!list.isEmpty()) {
        long sum = 0;
        int size = list.size();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            sum += node.val;
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        average.add(((double)sum)/size);
    }
    return average;
}