leetcode-cn Daily Challenge on September 12th, 2020.
leetcode Daily Challenge on March 5th, 2021.
Difficulty : Tree
Related Topics : Easy
Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array.
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].
- The range of node's value is in the range of 32-bit signed integer.
- mine
- Java
Runtime: 2 ms, faster than 82.50%, Memory Usage: 41.9 MB, less than 36.35% of Java online submissions
// O(N)time // O(D)space public List<Double> averageOfLevels(TreeNode root) { Map<Integer,Double> map = new HashMap<>(); Map<Integer,Integer> count = new HashMap<>(); dfs(root, map, count, 0); List<Double> res = new LinkedList<>(); int t = 0; while(map.containsKey(t)){ double v = map.get(t); int c = count.get(t); res.add(v / c); t++; } return res; } void dfs(TreeNode node, Map<Integer,Double> map, Map<Integer,Integer> count,int deep){ if(node == null) return; map.put(deep, map.getOrDefault(deep, 0D) + node.val); count.put(deep, count.getOrDefault(deep, 0) + 1); dfs(node.left, map, count, deep + 1); dfs(node.right, map, count, deep + 1); }
- Java