All problems

Above-Average Shelves

Medium · tree bfs

A jam shop displays its jars on tiered shelves, and the display is described as a binary tree. The top jar is the root. Each jar sits above up to two jars on the shelf below it, one on the left and one on the right. All the jars at the same depth form one shelf, and every jar has a sweetness score written on it.

For every shelf, from the top shelf to the bottom one, count the jars whose sweetness is strictly greater than the average sweetness of that shelf (the average is over all the jars on that shelf).

Return the counts as a list, one number per shelf, top to bottom. An empty display has no shelves, so return an empty list.

Examples

Example 1

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

Output: [0, 1, 1]

Shelf [3] has an average of 3 and nothing is above it. Shelf [9, 20] has an average of 14.5, so only 20 counts. Shelf [15, 7] has an average of 11, so only 15 counts.

Example 2

Input: root = [5, 5, 5]

Output: [0, 0]

Every jar on a shelf equals its average, so nothing is strictly above it.

Example 3

Input: root = []

Output: []

Constraints