Show problems as
Classic problem #1161MediumTreeDepth-First SearchBreadth-First SearchBinary Tree

Maximum Level Sum of a Binary Tree

Real-world version: Heaviest Tier of the Reporting Chart
Tracked in this browser only
Read Maximum Level Sum of a Binary Tree on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A company files a reporting chart. One unit sits at the top, and every unit has at most two units reporting to it, held in a first slot and a second slot; either slot may be empty. Each unit files a monthly balance, which may be negative.

The chart arrives as the flat list units, written tier by tier. units[0] is the balance of the top unit. Reading the list from left to right, every entry that is not null claims the next two unused positions as its first and second slot in that order, and null marks an empty slot. An entry that is null claims no positions of its own. If the list ends early, the slots that were never written are empty.

Tiers are numbered from 1: the top unit is on tier 1, the units reporting to it are on tier 2, and so on. A tier's total is the sum of the balances of the units on it.

Return the number of the tier with the largest total. If more than one tier ties for the largest total, return the smallest such tier number.

Examples

Example 1

Input
units = [4, 7, 9, 6, 5, null, 8]
Output
3

Tier 1 holds the top unit and totals 4. Tier 2 holds 7 and 9 and totals 16. The unit filing 7 owns the next two positions, 6 and 5; the unit filing 9 owns an empty slot and the unit filing 8. So tier 3 holds 6, 5 and 8 and totals 19.

Example 2

Input
units = [5, 2, 3]
Output
1

Tier 1 totals 5, and tier 2 holds 2 and 3, which also totals 5. The two tiers tie, so the smaller tier number is returned.

Example 3

Input
units = [8, null, 6, null, 7]
Output
1

The top unit's first slot is empty and its second slot holds the unit filing 6, so tier 2 totals 6. That unit's slots are empty and 7 in turn, so tier 3 totals 7. Tier 1 totals 8, the largest of the three.

Constraints

  • The chart holds between 1 and 10^4 units.
  • 1 <= units.length <= 3 * 10^4
  • -10^5 <= units[i] <= 10^5
  • units[0] is not null.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def heaviest_tier(units: list) -> int:
Java
public int heaviestTier(Integer[] units)

More on the same topics