Construct Binary Tree from Preorder & Inorder

Linked List Cycle II

Path Sum II

Rebuild a unique binary tree from its preorder and inorder traversal arrays.

Given two integer arrays `preorder` and `inorder` where `preorder` is the preorder traversal of a binary tree and `inorder` is the inorder traversal of the same tree, construct and return the binary tree.

You may assume all node values in the tree are **unique** (so any value can be located in `inorder` unambiguously).

**Input / output**
- Input: `preorder: int[]`, `inorder: int[]`
- Output: `TreeNode` (JSON test fixture is a LeetCode-style level-order array, e.g. `[3,9,20,null,null,15,7]`, with `null` for a missing child)

## Example
```json
Input: {"preorder":[3,9,20,15,7],"inorder":[9,3,15,20,7]}
Output: [3,9,20,null,null,15,7]
```

## Constraints
- 0 <= number of nodes <= 3,000
- `preorder` and `inorder` consist of unique values
- Every value in `inorder` also appears in `preorder`, and vice versa

## Follow-up
How would this change if node values were **not** guaranteed unique? What extra information would you need?

The key pattern is: the first element of any preorder slice is always that subtree's root, and looking up that value's position in the corresponding inorder slice splits the remaining nodes into the left and right subtrees.

Recognize the Pattern

Advance one state transition at a time. Mark or update state before exploring dependent work.

Build the Algorithm

Test empty or minimal input, skewed shapes, duplicates where allowed, and impossible outcomes.

Check Edge Cases

Time: O(n) — a hash map lookup gives each value's inorder index in O(1), so every node is built exactly once. Space: O(n) for the value-to-index map plus O(h) recursion stack (O(n) worst case on a skewed tree).

All 5 languages below run and submit against the remote judge for this problem — Java/Go/Rust use the same real TreeNode structural-type support the judge added for the rest of the linked-list/tree track.