Show problems as
Classic problem #114MediumLinked ListStackTreeDepth-First SearchBinary Tree

Flatten Binary Tree to Linked List

Real-world version: Straighten the Repair Plan
Tracked in this browser only
Read Flatten Binary Tree to Linked List on LeetCode(opens in a new tab)

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

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

Python
def straighten_plan(jobs: list) -> list:
Java
public Integer[] straightenPlan(Integer[] jobs)

More on the same topics