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

Construct Binary Tree from Inorder and Postorder Traversal

Real-world version: Rebuilding a Rig From Two Readings
Tracked in this browser only
Read Construct Binary Tree from Inorder 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 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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def build_tree(middle: list[int], after: list[int]) -> list:
Java
public Integer[] buildTree(int[] middle, int[] after)

More on the same topics