0233MediumLinked ListStackTreeDepth-First SearchBinary Tree

Straighten the Repair Plan

Tracked in this browser only

Trains the technique from

LeetCode 114Flatten Binary Tree to Linked List

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 workshop keeps a repair plan as a binary tree of jobs. A job may carry a prep branch on its left link and a follow-on branch on its right link.

One technician works the plan alone, always in this order: the job in hand, then the whole of that job's prep branch, then the whole of its follow-on branch.

Rewire the plan in place so that it becomes single file: every left link empty, and every right link pointing at the job the technician works next. Relink the jobs you were handed instead of assembling a second plan beside them.

The plan arrives as jobs, a level-order listing. jobs[0] is the top job's value, and the remaining entries give, level by level and left to right, the left link then the right link of every job already listed. A null entry marks an empty link, an empty link contributes no entries of its own, and trailing null entries are dropped. An empty list means the plan holds no jobs.

Return the level-order listing of the rewired plan, in that same format. Since every left link ends up empty, the listing you return alternates a job value with a null.

Examples

Example 1

Input: jobs = [4, 2, 6, 1, 3]
Output: [4, null, 2, null, 1, null, 3, null, 6]

Job 4 has prep branch 2 (holding 1 and 3) and follow-on branch 6, so the technician works 4, 2, 1, 3, 6 and the chain lists those values with an empty left link between them.

Example 2

Input: jobs = [8, null, 5, null, 2]
Output: [8, null, 5, null, 2]

No job has a prep branch, so the working order is already 8, 5, 2 and the listing comes back unchanged.

Example 3

Input: jobs = [1, 2, null, null, 3]
Output: [1, null, 2, null, 3]

Job 1 has prep branch 2, and job 2 has no prep branch but a follow-on branch 3, giving the working order 1, 2, 3.

Constraints

The number of jobs is in the range [0, 2000]
-100 <= job value <= 100
jobs is a valid level-order listing of a binary tree

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 straighten_plan(jobs: list) -> list:

Java

public Integer[] straightenPlan(Integer[] jobs)

The intended approach

Time O(n)Space O(n) for the rebuilt tree and the returned listing, O(1) beyond them

Rebuild the tree from the listing by handing two entries to each job in the order jobs are discovered, which is the order the listing was written in. Then walk down the right links with a loop: whenever the current job has a prep branch, find the last job of that branch by following its right links, hang the current follow-on branch off that last job, move the prep branch into the right link and empty the left link. Finally serialise the rewired tree level by level. The rewiring stage adds no data structure of its own, and the loop replaces recursion so a 2000-job plan is safe.

Pythonentry point: straighten_plan

def _rebuild(jobs):
    if not jobs or jobs[0] is None:
        return None
    root = [jobs[0], None, None]
    order = [root]
    head = 0
    cursor = 1
    while head < len(order) and cursor < len(jobs):
        node = order[head]
        head += 1
        for slot in (1, 2):
            if cursor >= len(jobs):
                break
            value = jobs[cursor]
            cursor += 1
            if value is not None:
                node[slot] = [value, None, None]
                order.append(node[slot])
    return root


def _listing(root):
    if root is None:
        return []
    out = []
    queue = [root]
    head = 0
    while head < len(queue):
        node = queue[head]
        head += 1
        if node is None:
            out.append(None)
        else:
            out.append(node[0])
            queue.append(node[1])
            queue.append(node[2])
    while out and out[-1] is None:
        out.pop()
    return out


def straighten_plan(jobs):
    root = _rebuild(jobs)
    node = root
    while node is not None:
        if node[1] is not None:
            tail = node[1]
            while tail[2] is not None:
                tail = tail[2]
            tail[2] = node[2]
            node[2] = node[1]
            node[1] = None
        node = node[2]
    return _listing(root)

The obvious version

Collect the working order into a list with an explicit stack that pushes the follow-on branch before the prep branch, then write out the listing that a single-file chain of those values must have.

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 _rebuild(jobs):
    if not jobs or jobs[0] is None:
        return None
    root = [jobs[0], None, None]
    order = [root]
    head = 0
    cursor = 1
    while head < len(order) and cursor < len(jobs):
        node = order[head]
        head += 1
        for slot in (1, 2):
            if cursor >= len(jobs):
                break
            value = jobs[cursor]
            cursor += 1
            if value is not None:
                node[slot] = [value, None, None]
                order.append(node[slot])
    return root


def bf_straighten_plan(jobs):
    # Read the working order off the original plan with an explicit stack, then
    # write down the listing a single-file chain of those values must have.
    root = _rebuild(jobs)
    order = []
    stack = [root] if root is not None else []
    while stack:
        node = stack.pop()
        order.append(node[0])
        if node[2] is not None:
            stack.append(node[2])
        if node[1] is not None:
            stack.append(node[1])
    out = []
    for index, value in enumerate(order):
        if index:
            out.append(None)
        out.append(value)
    return out

How this problem was checked

Reference solution executed against 11 test cases — 11 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