Implement tree construction from preorder and inorder arrays.
Optimization tips:
- Build a hash map: value → index in inorder
- Pass indices (preStart, preEnd, inStart, inEnd) instead of slicing
- This reduces time from to
Here's the trick: the number of elements in the left subtree in inorder equals the number of elements after the root in preorder's left portion.
Test on trees of various shapes: complete, skewed left, skewed right, single node. Time: . Space: .