1025MediumArrayHash TableDivide and ConquerTreeBinary Tree

Rebuilding a Rig From Two Readings

Tracked in this browser only

Trains the technique from

LeetCode 106Construct Binary Tree from Inorder and Postorder 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.

A cargo rig hangs from a single top joint. Every joint carries at most two joints below it, in a first and a second slot, and either slot may be empty. No two joints carry the same load.

Two readings of the rig are given. The middle reading middle visits everything hanging in a joint's first slot, then the joint itself, then everything in its second slot. The after reading after visits everything in the first slot, then everything in the second slot, then the joint itself. Both readings describe the same rig.

Return the rig as a flat list read level by level: the first entry is the top joint's load, and reading left to right, every entry that is not null claims the next two unused positions as its first and second slot in that order, while null marks an empty slot and claims no positions of its own. No null is left trailing at the end.

Examples

Example 1

Input: middle = [4, 2, 5, 1, 6, 3, 7], after = [4, 5, 2, 6, 7, 3, 1]
Output: [1, 2, 3, 4, 5, 6, 7]

The after reading ends on 1, so 1 is the top joint. In the middle reading, 4, 2, 5 sit before it and 6, 3, 7 after it, so those three hang in the first slot and these three in the second. Repeating that inside each piece gives 2 and 3 below the top, with 4, 5, 6 and 7 hanging bare beneath them.

Example 2

Input: middle = [-1], after = [-1]
Output: [-1]

A single load means a single joint with both slots empty.

Example 3

Input: middle = [3, 2, 1], after = [1, 2, 3]
Output: [3, null, 2, null, 1]

The after reading ends on 3, and the middle reading has nothing after 3, so its second slot is empty and everything hangs down the first slots in a single file.

Constraints

1 <= middle.length <= 3000
after.length == middle.length
-3000 <= middle[i] <= 3000
-3000 <= after[i] <= 3000
No two loads are alike.
The two readings describe the same rig.

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 build_tree(middle: list[int], after: list[int]) -> list:

Java

public Integer[] buildTree(int[] middle, int[] after)

The intended approach

Time O(n) over the readings' length.Space O(n) for the table and the rebuilt rig.

The last entry of the after reading is the top joint, because that reading always leaves a joint until after everything below it. Finding that load in the middle reading cuts it in two: everything before it hangs in the first slot and everything after it in the second, since the middle reading covers a whole first slot, then the joint, then a whole second slot. The sizes of those two pieces then cut the after reading the same way, its opening stretch being the first slot's contents and the next stretch the second slot's, with the joint last of all. Each piece is the same problem again, so recursing settles the whole rig. Scanning the middle reading for each load would cost its length every time, so build a table from load to place once, up front. Then walk the after reading from the back, carrying the bounds within the middle reading, and build the second slot before the first, which is the order the backwards walk hands the loads over in. Writing the answer out goes level by level: for each level, put out two entries per filled joint of the level above, using `null` for an empty slot, and stop once a level holds no joints, which is what leaves nothing trailing.

Pythonentry point: build_tree

def build_tree(middle, after):
    where = {}
    for at, value in enumerate(middle):
        where[value] = at
    n = len(after)
    load = []
    slot1 = []
    slot2 = []
    def fresh(value):
        load.append(value)
        slot1.append(None)
        slot2.append(None)
        return len(load) - 1
    cursor = [n - 1]
    def grow(lo, hi):
        if lo > hi:
            return None
        value = after[cursor[0]]
        cursor[0] -= 1
        made = fresh(value)
        split = where[value]
        slot2[made] = grow(split + 1, hi)
        slot1[made] = grow(lo, split - 1)
        return made
    top = grow(0, n - 1)
    if top is None:
        return []
    out = [load[top]]
    level = [top]
    while True:
        chunk = []
        nxt = []
        for node in level:
            for child in (slot1[node], slot2[node]):
                if child is None:
                    chunk.append(None)
                else:
                    chunk.append(load[child])
                    nxt.append(child)
        if not nxt:
            break
        out.extend(chunk)
        level = nxt
    return out

The obvious version

Do the same cutting but with plain copies: take the last entry of the after reading as the joint, search the middle reading for it, and hand the two halves of each reading to the same routine as fresh lists. Costs a search and a copy per joint, so the readings' length squared, rather than one table lookup apiece.

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_build_tree(middle, after):
    def grow(mid, post):
        if not mid:
            return None
        value = post[len(post) - 1]
        at = mid.index(value)
        return (value,
                grow(mid[:at], post[:at]),
                grow(mid[at + 1:], post[at:len(post) - 1]))
    root = grow(list(middle), list(after))
    if root is None:
        return []
    out = [root[0]]
    level = [root]
    while True:
        chunk = []
        nxt = []
        for node in level:
            for child in (node[1], node[2]):
                if child is None:
                    chunk.append(None)
                else:
                    chunk.append(child[0])
                    nxt.append(child)
        if not nxt:
            break
        out.extend(chunk)
        level = nxt
    return out

How this problem was checked

Reference solution executed against 14 test cases — 14 passed
3 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