Construct Binary Tree from Preorder and Inorder Traversal

You get two lists, preorder and inorder. Both hold the values of one binary tree, in two different orders:

• preorder: a node, then its left subtree, then its right subtree.
• inorder: a node's left subtree, then the node, then its right subtree.

Rebuild the tree and return its root. No value appears twice.

The tests print your tree row by row from the top. Each row goes left to right. A missing child is written as null. The nulls at the end are left out. So [5,null,8] is a root 5 with only a right child, 8.

Example 1:

Input: preorder = [10,4,8,2,7], inorder = [8,4,10,7,2]
Output: [10,4,2,8,null,7]
      10
     /  \
    4    2
   /    /
  8    7

Explanation: The root is 10.
Its left child is 4, and 8 is the left child of 4.
Its right child is 2, and 7 is the left child of 2.

Example 2:

Input: preorder = [-7], inorder = [-7]
Output: [-7]
Explanation: With one value, the tree is just a root.

Example 3:

Input: preorder = [6,9,3], inorder = [6,3,9]
Output: [6,null,9,3]
  6
   \
    9
   /
  3

Explanation: The root 6 has no left child.
Its right child is 9.
3 is the left child of 9.
The output writes null for the missing left child of 6.

Constraints:

• Each list has 1 to 3,000 values.
• Both lists have the same length.
• Each value is a whole number from -3,000 to 3,000.
• The tree is at most 400 levels deep.