Show problems as
Classic problem #889MediumArrayHash TableDivide and ConquerTreeBinary Tree

Construct Binary Tree from Preorder and Postorder Traversal

Real-world version: Rebuilding The Inspection Rig
Tracked in this browser only
Read Construct Binary Tree from Preorder and Postorder Traversal on LeetCode(opens in a new tab)

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

Learn the pattern firstConstruction · Binary Trees & BST, animated step by step

A parcel line is built as a binary tree of inspection stations. Every station has a distinct label and at most two downstream stations, one on its left branch and one on its right.

A single parcel is pushed through the whole rig. Two logs come out of that run:

  • entry_log records a station's label the moment the parcel arrives at it, which happens before the parcel goes down that station's left branch and then its right branch;
  • exit_log records a station's label once both of its branches have been fully worked, so a station is written only after every station below it.

Rebuild the rig. When the two logs do not pin down which side a lone downstream station sits on, put it on the left: for every station that has at least one downstream station, the label written immediately after it in entry_log is its left branch station.

Return the rebuilt rig as a flat level-order encoding: entry 0 is the root's label, and after that, taking the present stations in level-order, each one contributes the next two entries as its left slot and then its right slot, with null for an absent station. Drop trailing null entries.

Examples

Example 1

Input
entry_log = [3, 5, 1, 2], exit_log = [1, 5, 2, 3]
Output
[3, 5, 2, 1]

Station 3 is the root, station 5 sits on its left branch with station 1 below 5, and station 2 sits on the root's right branch. Running a parcel through that rig writes 3, 5, 1, 2 on arrival and 1, 5, 2, 3 on completion, which is exactly the pair given.

Example 2

Input
entry_log = [4, 1], exit_log = [1, 4]
Output
[4, 1]

Station 4 is the root and station 1 is its only downstream station. The logs do not say which branch it hangs from, and the stated rule puts it on the left.

Example 3

Input
entry_log = [2, 6, 5, 1, 3, 4], exit_log = [5, 1, 6, 4, 3, 2]
Output
[2, 6, 3, 5, 1, 4]

Root 2 has station 6 on its left and station 3 on its right; station 6 has 5 and 1 below it, and station 3 has 4 on its left. Both logs read back off that rig unchanged.

Constraints

  • 1 <= entry_log.length <= 30
  • exit_log.length == entry_log.length
  • 1 <= entry_log[i] <= 30
  • 1 <= exit_log[i] <= 30
  • The labels are the integers from 1 to the number of stations, each appearing once in each log.
  • The two logs are guaranteed to come from one run over a single binary rig.

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 rebuild_station_tree(entry_log: list[int], exit_log: list[int]) -> list:
Java
public Integer[] rebuildStationTree(int[] entryLog, int[] exitLog)

More on the same topics