0427HardStringTreeDepth-First SearchBinary Tree

Rebuild the Inspection Line

Tracked in this browser only

Trains the technique from

LeetCode 1028Recover a Tree From Preorder Traversal

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def recover_from_preorder(log: str) -> list[int | None]:

Java

public Integer[] recoverFromPreorder(String log)

The intended approach

Time O(L + n) for a line of L characters describing n junctions: each character is read once, each junction is pushed and popped at most once, and the band walk touches each junction and each empty slot once.Space O(n) for the pair list, the stack and the queue, plus the returned listing, whose length stays under 2n.

One sweep of the line turns it into a list of (dash count, reading) pairs, gathering each reading digit by digit so multi-digit meters survive. A second sweep hangs the junctions: a stack holds the chain of junctions from the intake down to the one just placed, so trimming it to the incoming dash count leaves the junction that feeds the new one on top. That feeder takes the new junction as its first outlet if it has none yet and as its second otherwise, which is exactly the rule for a lone outlet. A band-by-band walk then emits the listing, queueing two slots for each junction written and none for an empty slot, and trims the trailing empty slots.

Pythonentry point: recover_from_preorder

def recover_from_preorder(log):
    # Read the line once into (depth, reading) pairs, then hang each junction on
    # the deepest ancestor still open: a stack indexed by depth does that, and it
    # is trimmed to the incoming depth before every hang. No nesting anywhere, so
    # a network 1000 steps deep is fine.
    span = len(log)
    depths = []
    readings = []
    at = 0
    while at < span:
        steps = 0
        while at < span and log[at] == "-":
            steps += 1
            at += 1
        value = 0
        while at < span and log[at] != "-":
            value = value * 10 + (ord(log[at]) - 48)
            at += 1
        depths.append(steps)
        readings.append(value)

    count = len(readings)
    first = [-1] * count
    second = [-1] * count
    open_chain = []
    for idx in range(count):
        while len(open_chain) > depths[idx]:
            open_chain.pop()
        if open_chain:
            feeder = open_chain[-1]
            if first[feeder] == -1:
                first[feeder] = idx
            else:
                second[feeder] = idx
        open_chain.append(idx)

    listing = []
    queue = [0]
    head = 0
    while head < len(queue):
        node = queue[head]
        head += 1
        if node == -1:
            listing.append(None)
            continue
        listing.append(readings[node])
        queue.append(first[node])
        queue.append(second[node])
    while listing and listing[-1] is None:
        listing.pop()
    return listing

The obvious version

Split by scanning. Inside a stretch of the pair list, the first pair is the junction; scan the rest of the stretch for the positions exactly one dash deeper, which are where its outlets begin. Recurse on the stretch from the first such position to the second, and on the stretch from the second to the end, building a nested structure that is then read band by band. O(n^2).

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_recover_from_preorder(log):
    pieces = []
    at = 0
    span = len(log)
    while at < span:
        steps = 0
        while at < span and log[at] == "-":
            steps += 1
            at += 1
        start = at
        while at < span and log[at] != "-":
            at += 1
        pieces.append((steps, int(log[start:at])))

    def shape(lo, hi):
        if lo >= hi:
            return None
        depth = pieces[lo][0]
        breaks = []
        for probe in range(lo + 1, hi):
            if pieces[probe][0] == depth + 1:
                breaks.append(probe)
        if not breaks:
            return [pieces[lo][1], None, None]
        if len(breaks) == 1:
            return [pieces[lo][1], shape(breaks[0], hi), None]
        return [pieces[lo][1], shape(breaks[0], breaks[1]), shape(breaks[1], hi)]

    tree = shape(0, len(pieces))
    listing = []
    row = [tree]
    while row:
        nxt = []
        for spot in row:
            if spot is None:
                listing.append(None)
            else:
                listing.append(spot[0])
                nxt.append(spot[1])
                nxt.append(spot[2])
        row = nxt
    while listing and listing[-1] is None:
        listing.pop()
    return listing

How this problem was checked

Reference solution executed against 14 test cases — 14 passed
5 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in