436. Average of Levels in Binary Tree
Your function receives root, the root of a binary tree of integers. For every depth of the tree — the root is depth 0, its children depth 1, and so on — compute the average of all node values at that depth.
Return the averages as a list ordered from the root's level downward. Each average is a real number (it need not be an integer); your answer is printed with exactly five digits after the decimal point, so return the exact quotient sum / count for each level and let the harness handle formatting.
Example 1:
Input: root = [3, 9, 20, null, null, 15, 7]
Output: [3.00000, 14.50000, 11.00000]
Explanation: Depth 0 holds just 3. Depth 1 holds 9 and 20, averaging (9 + 20) / 2 = 14.5. Depth 2 holds 15 and 7, averaging 22 / 2 = 11.
Example 2:
Input: root = [1, 2, 3, 4, 5, 6, 7]
Output: [1.00000, 2.50000, 5.50000]
Explanation: A perfect tree: level averages are 1, (2 + 3) / 2 = 2.5, and (4 + 5 + 6 + 7) / 4 = 5.5.
Constraints:
- 1 ≤ number of nodes ≤ 10⁴
- -10⁵ ≤ Node.val ≤ 10⁵
Hints:
You need every node grouped by its depth. Either traversal works: a breadth-first search visits the tree level by level natively, while a depth-first search can carry the current depth as a parameter and drop each value into a per-depth bucket.
For the BFS: put the root in a queue, and on each round record the queue's current size k — exactly the nodes of one level. Pop exactly k nodes, sum their values, push their children, and emit sum / k before starting the next round. Sum in a wide integer type before dividing once.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: root = [3, 9, 20, null, null, 15, 7]
Expected output: [3.00000, 14.50000, 11.00000]