106. Construct Binary Tree from Inorder and Postorder Traversal
You receive two integer arrays describing the same binary tree: inorder holds its values in inorder sequence (left subtree, node, right subtree) and postorder holds them in postorder sequence (left subtree, right subtree, node). Every value in the tree is distinct. Reconstruct the unique tree behind these two walks and return its root.
The useful observation: the final entry of postorder is always the root, and finding that value inside inorder splits the remaining values into the left and right subtrees — a split you can keep applying recursively.
Your returned tree is checked structurally: the judge prints it in level order with null marking a missing child of a present node, dropping any trailing null markers.
Example 1:
Input: inorder = [9, 3, 15, 20, 7], postorder = [9, 15, 7, 20, 3]
Output: [3, 9, 20, null, null, 15, 7]
Explanation: The last postorder value, 3, is the root. In inorder, 9 lies to its left (the whole left subtree) while 15, 20, 7 lie to its right; repeating the split on that right chunk makes 20 a child of 3 with children 15 and 7.
Example 2:
Input: inorder = [-1], postorder = [-1]
Output: [-1]
Explanation: A single value is a single-node tree.
Constraints:
- 1 ≤ inorder.length ≤ 2000
- postorder.length == inorder.length
- -3000 ≤ inorder[i], postorder[i] ≤ 3000
- All values are distinct, and both arrays are traversals of the same valid binary tree.
Hints:
One traversal alone cannot fix the shape, but postorder hands you something for free: its very last entry is the root of the whole tree.
Locate that root value inside `inorder`. Everything before it is the left subtree's inorder; everything after it is the right subtree's. The postorder array carves into the same-sized blocks (left block, right block, root), so you can recurse on matching pieces.
Rescanning `inorder` for every root costs O(n²). Precompute a hash map value → inorder index, and instead of slicing arrays, walk one pointer backwards through `postorder`, building each node's right subtree before its left.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: inorder = [9, 3, 15, 20, 7], postorder = [9, 15, 7, 20, 3]
Expected output: [3, 9, 20, null, null, 15, 7]