二叉树的层平均值

给定一个非空二叉树, 返回一个由每层节点平均值组成的数组.

示例 1:

输入:

    3
   / \
  9  20
    /  \
   15   7

输出: [3, 14.5, 11]
解释:
第0层的平均值是 3, 第1层是 14.5, 第2层是 11. 因此返回 [3, 14.5, 11].
注意：

节点值的范围在32位有符号整数范围内。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/average-of-levels-in-binary-tree

分析：
此题基于BFS(breadth first search)广度优先搜索。
下面先给出图的BFS算法的伪码：

BFS(G, s)
// B=所有边界点构成的集合
B.inQueue(s);
WHILE B非空
	d = B.outQueue(s);
	将d标记为已遍历;
	FOR d的所有邻居t
		IF t的标记为未遍历
			B.inQueue(t);
	ENDFOR
ENDWHILE

根据BFS的框架，可以横向把节点全部加入队列。那么要计算一层节点的值的和，就需要控制每次while循环队列弹出的个数就是当前层的个数。进入for循环前先记录队列内元素个数，之后边出队边入队即可。

/**
 * 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) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<Double> res = new ArrayList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            int size = queue.size();
            double sum = 0;
            for(int i = 0; i < size; ++i) {
                TreeNode temp = queue.poll();
                if(temp.left != null) queue.offer(temp.left);
                if(temp.right != null) queue.offer(temp.right);
                sum += temp.val;
            }
            res.add(sum/size);
        }
        return res;
    }
}