Show problems as
Classic problem #1028HardStringTreeDepth-First SearchBinary Tree

Recover a Tree From Preorder Traversal

Real-world version: Rebuild the Inspection Line
Tracked in this browser only
Read Recover a Tree From Preorder Traversal on LeetCode(opens in a new tab)

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

An inspector walks a pipeline that branches downstream from a single intake. Every junction carries a flow-meter reading. A junction feeds at most two junctions below it, called its first and second outlet, and when a junction feeds only one junction that one is its first outlet.

Her walk goes into a single line log. She notes a junction's reading, then everything reachable through its first outlet, then everything reachable through its second outlet, following that same order at every junction she reaches. Each reading is written after one '-' for each step the junction lies below the intake, so the intake's reading opens the line with no dash and a junction three steps down carries three dashes. A reading is plain decimal digits, and dashes are the only other character in the line.

Rebuild the pipeline and return it as a band listing, one band at a time from the intake down, and left to right within a band. Slot 0 holds the intake. Each junction that appears in the listing takes the next two unclaimed slots for what it feeds, the first outlet then the second. A slot holding null means nothing is fed there, and such a slot claims no slots of its own. Slots that would hold null at the very end of the listing must be left off.

Exactly one pipeline matches a given line, so the listing is unique.

Examples

Example 1

Input
log = "5-3--8--9-4--2"
Output
[5, 3, 4, 8, 9, 2]

The intake reads 5 and feeds 3 and 4. Junction 3 feeds 8 and 9, and junction 4 feeds only 2, which therefore sits on its first outlet.

Example 2

Input
log = "10-200--3000-45"
Output
[10, 200, 45, 3000]

Four meters, two of them multi-digit beyond two places. The intake reads 10, its first outlet reads 200 with 3000 below it, and its second outlet reads 45.

Example 3

Input
log = "1-2--3--4-5"
Output
[1, 2, 5, 3, 4]

After the reading 4, which lies two steps below the intake, the reading 5 carries a single dash, so it sits one step below the intake alongside 2.

Example 4

Input
log = "7"
Output
[7]

A single reading with no dash: the pipeline is one junction and nothing is fed from it.

Example 5

Input
log = "1-2--3"
Output
[1, 2, null, 3]

Each reading is one dash deeper than the one before it, so the pipeline runs straight down through first outlets and the empty second outlets show up inside the listing.

Constraints

  • The number of junctions is in the range [1, 1000].
  • 1 <= reading <= 10^9
  • log is the walk of some pipeline built as described, so its first reading carries no dash and no reading is more than one dash deeper than the reading before it.

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 recover_from_preorder(log: str) -> list[int | None]:
Java
public Integer[] recoverFromPreorder(String log)

More on the same topics