Average of Levels in Binary Tree

Easy·Tagstreebfsqueuemath

Problem Statement

Given the `root` of a binary tree, return the average value of the nodes on each level in the form of an array. Answers within `10^-5` of the actual answer will be accepted. Note: Assume a standard `TreeNode` class is already provided in the execution environment, containing `val`, `left`, and `right` properties.

Examples

Example 1

Input

root: [3, 9, 20, null, null, 15, 7]

Tree

Output

"[3.00000, 14.50000, 11.00000]"

Why

The average value of nodes on level 0 is 3.0. The average value of nodes on level 1 is (9 + 20) / 2 = 14.5. The average value of nodes on level 2 is (15 + 7) / 2 = 11.0.

Example 2

Input

root: [3, 9, 20, 15, 7]

Tree

Output

"[3.00000, 14.50000, 11.00000]"

Why

Level 0: 3.0, Level 1: 14.5, Level 2: 11.0.

Constraints

•The number of nodes in the tree is in the range [1, 10^4].
•-2^31 <= Node.val <= 2^31 - 1

Hints

Stuck? Reveal a nudge toward the right pattern, one step at a time.

Hint 1

Just like standard Level Order Traversal, you can use a Queue to process the tree level by level.

Hint 2

Instead of storing all the nodes of a level in an array, simply keep a running `sum` inside the `for` loop.

Hint 3

Be careful! Node values can be as large as `2^31 - 1`. If a level has many large numbers, an integer `sum` will overflow. Use a 64-bit float or a `long` to store your sum.

Hint 4

After the `for` loop finishes processing the level, divide your `sum` by the `levelSize` and append it to your results array.