637. 二叉树的层平均值

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

示例 1：

输入：
    3
   / \
  9  20
    /  \
   15   7
输出：[3, 14.5, 11]
解释：
第 0 层的平均值是 3 ,  第1层是 14.5 , 第2层是 11 。因此返回 [3, 14.5, 11] 。

提示：

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

思路

借助102. 二叉树的层序遍历思路即可。注意int的和有可能越界，所以最好先转double再求和。

解法

class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(root);
        double sum = 0;
        while (!deque.isEmpty()) {
            int len = deque.size();
            sum = 0;
            for (int i = 0; i < len; i++) {
                root = deque.pop();
                //避免sum超出int范围
                sum += (double) root.val;
                if (root.left != null) {
                    deque.offer(root.left);
                }
                if (root.right != null) {
                    deque.offer(root.right);
                }
            }
            result.add(sum / len);
        }
        return result;
    }
}