AverageOfLevelsInBinaryTree [source code]

public class AverageOfLevelsInBinaryTree {
static
/******************************************************************************/
public class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> res = new LinkedList<>();
        if (root == null) return res;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            long sum = 0;
            int size = queue.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);
            }
            res.add((double) sum / size);
        }
        return res;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        AverageOfLevelsInBinaryTree.Solution tester = new AverageOfLevelsInBinaryTree.Solution();
    }
}

题目本身很简单, 就是注意一个sum要防止overflow; 最后的速度是9ms (91%), 好像是submission最优解了;

这个题目如果用DFS好像也是很简单的, 直接给每个node直接tag上自己的depth(number of level)就行了; 同时所有的tag全部都count起来(用一个hash array: hash[depth] = count), 最后过一遍转换成一个list就行了;

editorial上面也是这两个思路好像, 一个DFS一个BFS, DFS那个没仔细看了;

discussion也没有什么好的思路;

Problem Description

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.
Difficulty:Easy
Total Accepted:5.6K
Total Submissions:9.2K
Contributor: yangshun
Companies
facebook
Related Topics
tree
Similar Questions
Binary Tree Level Order Traversal Binary Tree Level Order Traversal II