Problem
You are given the preorder and postorder traversals of a binary tree whose node values are distinct. Reconstruct one binary tree consistent with both traversals. Some traversal pairs do not identify a unique tree, so the contract below defines a deterministic choice.
Function Contract
Implement reconstruct_tree(preorder, postorder) and return the reconstructed tree as a level-order list. Use null for missing children and remove trailing null values from the returned list.
Rules
-
The inputs describe the same valid binary tree and contain the same distinct values.
-
For an ambiguous node with exactly one child, attach that child on the left.
-
For a node with two children, preserve their relative left-to-right order from both traversals.
-
The returned tree must reproduce the given preorder and postorder traversals exactly.
-
Do not enumerate all possible trees.
Constraints
-
1 <= len(preorder) == len(postorder) <= 100000
.
-
All node values are distinct signed 32-bit integers.
-
Account for linear tree depth rather than assuming a balanced tree.
Examples
preorder = [1, 2, 3]
postorder = [3, 2, 1]
output = [1, 2, null, 3]
The traversals are ambiguous; the deterministic rule places each single child on the left.