Construct Tree from Traversal Arrays

Given two integer arrays **preorder** and **inorder** where:

- `preorder` is the preorder traversal of a binary tree

- `inorder` is the inorder traversal of the same tree

Construct and return the binary tree. Return the level-order representation.

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]

Output: [3,9,20,null,null,15,7]

Classic reconstruction.

Input: preorder = [-1], inorder = [-1]

Output: [-1]

Single node.

Time

O(n) with a hash map for inorder indices.

Space

O(n)

#1 Classic case

Input: pre=[3,9,20,15,7] in=[9,3,15,20,7]

Expected: [3,9,20,null,null,15,7]

#2 Single node

Input: pre=[-1] in=[-1]

Expected: [-1]

#3 Root with left child

Input: pre=[1,2] in=[2,1]

Expected: [1,2]