Show problems as
Classic problem #366MediumTreeDepth-First SearchBinary TreeDP on Trees

Find Leaves of Binary Tree

Real-world version: Rounds of Unhooking a Light Rig
Tracked in this browser only
Read Find Leaves of Binary Tree on LeetCode(opens in a new tab)

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

A stage crew has rigged a hanging light frame. A single bar hangs from the roof beam, and every bar carries at most two bars below it, one on its left arm and one on its right arm. No bar is ever hung from two arms at once, so the frame branches downward and never joins back up. Each bar is stencilled with a load code, which is negative when the bar is counterweighted.

The frame reaches you as rig, which lists the bars one level at a time from the roof beam downward, left to right inside a level. Slot 0 holds the top bar. Reading the listing from the front, every bar takes the next two slots that no bar has taken yet: the first of the two belongs to its left arm and the second to its right arm. A slot holding null means that arm carries nothing, and an empty arm takes no slots of its own. null slots at the very end of the listing may be left out.

The frame comes down in rounds. In one round the crew unhooks every bar that has nothing at all hanging beneath it as the round begins; a bar that only becomes free part way through the round waits for the next round. Rounds continue until no bar is left.

Return one entry per round, in the order the rounds take place. Each entry lists the load codes unhooked in that round, ordered by the slot the bar occupies in rig.

Examples

Example 1

Input
rig = [10, 20, 30, 40, 50]
Output
[[30, 40, 50], [20], [10]]

Slots 2, 3 and 4 hold bars with empty arms, so those three come off first, in listing order. That leaves the bar in slot 1 free for the second round, and the top bar alone for the third.

Example 2

Input
rig = [4, 2, null, 9]
Output
[[9], [2], [4]]

The top bar has only a left arm, and so does the bar hanging from it, so one bar comes off in each of the three rounds.

Example 3

Input
rig = [5]
Output
[[5]]

The rig is a single bar with both arms empty, so one round clears it.

Example 4

Input
rig = [-100, 100, -100, null, null, 0, 7]
Output
[[100, 0, 7], [-100], [-100]]

In the first round the bars in slots 1, 5 and 6 have nothing beneath them and are unhooked in that order. The bar in slot 2 is then free for the second round, and the top bar for the third.

Constraints

  • The number of bars in the rig is in the range [1, 100].
  • -100 <= load code of a bar <= 100
  • rig[0] holds a bar.
  • Every slot in rig that is not null was taken by an arm of an earlier bar.

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 dismantle_rounds(rig: list[int | None]) -> list[list[int]]:
Java
public List<List<Integer>> dismantleRounds(Integer[] rig)

More on the same topics