Reconstruct a binary tree from its inorder and postorder traversal arrays.
Problem
You are given two integer arrays inorder and postorder that represent the inorder and postorder traversal of the same binary tree with unique values.
Your task is to build and return the original binary tree.
Because the values are unique, the tree is guaranteed to be reconstructible from these traversals.
Input Format
inorder: an array of unique integers representing an inorder traversal.postorder: an array of the same unique integers representing a postorder traversal.
Both arrays describe the same binary tree.
Output Format
Return the root of the reconstructed binary tree.
Constraints
- The tree nodes contain unique values.
inorder.length == postorder.length- The traversal arrays describe the same binary tree.
- Typical interview setting: (implementation should be efficient).
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 is 3, so 3 is the root. In inorder, 9 is on the left of 3 and 15,20,7 are on the right. Repeating the process reconstructs the full tree.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.