Approach Summary
Preorder[0] is always the root. Find its index in inorder to split left/right subtrees. Recurse with slices.
How to Recognize This Pattern
- Preorder root + inorder split → two subtrees
- Use HashMap for O(1) inorder index lookup
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(n)
Tags
Array Hash Table Divide and Conquer Tree Binary Tree