467. Floor Averages
A hotel keeps the number of guests in each room in a binary tree rooted at root: the root is the top floor, its children the next floor down, and so on level by level. The manager wants one figure per floor, the average of the guest counts stored on that level.
Return an array of the averages, one per level, from the top level down to the deepest one. For an empty tree return an empty array. Values can be as large as a 32-bit integer in magnitude, so make sure a level's sum does not overflow. Answers are accepted with an absolute error of up to 10^-6.
Example 1
- Input:
- root = [10,4,6,-2,8,null,12]
- Output:
- [10,5,6]
- Explanation:
Level averages are 10, (4+6)/2 = 5 and (-2+8+12)/3 = 6.
Example 2
- Input:
- root = [5,2,3,1]
- Output:
- [5,2.5,1]
- Explanation:
Level averages are 5, (2+3)/2 = 2.5 and 1.
Constraints
0 ≤ number of nodes in root ≤ 1000
-231 ≤ Node.val ≤ 231 - 1
How this problem is judged
- Answers
- Numbers are accepted within a tolerance of 1.0E-6: |answer - expected| <= 1.0E-6 x max(1, |expected|).
- Tolerance
0.000001- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n)
- Space
- O(w)