Build Binary Tree From Preorder and Inorder Traversals

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, reconstruct and return the binary tree. You may assume all node values are unique.

Example 1

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

Output (level-order): [3, 9, 20, null, null, 15, 7]

      3
     / \
    9  20
       / \
      15  7

Example 2

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

Output: a single-node tree with value -1.

Constraints

• 1 <= preorder.length == inorder.length <= 3000.
• preorder and inorder both consist of unique values.
• Every value in inorder also appears in preorder (they represent the same tree).