542. Construct Binary Tree from Preorder and Postorder Traversal
Two integer arrays record walks over the same binary tree of distinct values: preorder (root, then left subtree, then right subtree) and postorder (left subtree, then right subtree, then root). Rebuild the tree.
A preorder/postorder pair cannot always tell left from right: when a node has exactly one child, both walks look identical whichever side the child hangs on. To make the answer unique, resolve every such ambiguity by attaching the lone child as the left child.
Your function receives preorder and postorder and returns the root of the rebuilt tree (a TreeNode). The judge prints your tree in level order — for every visited node it lists both children, writing null where a child is missing, then trims trailing nulls.
Example 1:
Input: preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]
Output: [1,2,3,4,5,6,7]
Explanation: preorder[0] = 1 is the root and preorder[1] = 2 heads the left subtree. In postorder, 2 closes its subtree at index 2, so the left subtree holds 3 nodes {4, 5, 2} and the rest {6, 7, 3} is the right subtree. Recursing rebuilds the full tree: 2 has children 4 and 5, 3 has children 6 and 7.
Example 2:
Input: preorder = [1,2,3], postorder = [3,2,1]
Output: [1,2,null,3]
Explanation: Each node has a single child, so the walks alone cannot say which side the children hang on. The canonical rule pins them: 2 becomes the left child of 1, and 3 the left child of 2.
Constraints:
- 1 ≤ preorder.length = postorder.length ≤ 2000
- 1 ≤ preorder[i] ≤ 10⁶, all values distinct
- postorder is a permutation of preorder, and the pair describes at least one valid binary tree
- Single-child ambiguities must resolve to the left child (canonical form).
Hints:
preorder starts with the root; postorder ends with it. The interesting element is preorder[1] — it is the root of the left subtree. Where does that value sit in postorder, and what does its position tell you about the left subtree's size?
Once you know the left subtree covers s nodes, both arrays split cleanly: preorder[1..s] / postorder[0..s-1] rebuild the left child, and the remaining middle sections rebuild the right child. Recurse.
For one pass, walk preorder pushing nodes onto a stack, and keep a pointer into postorder: whenever the stack top equals postorder[pointer], that subtree is finished — pop and advance. Attach each new node to the first free slot (left first) of the stack top.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]
Expected output: [1,2,3,4,5,6,7]