Construct Tree from Inorder and Preorder Traversal

Given two integer arrays inorder and preorder 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.

Class TreeNode:
    val (int)
    left (TreeNode)
    right (TreeNode)

Input Format

First Parameter - number n1

Second Parameter - number n2

Third Parameter - Array of numbers preorder of size n1

Fourth Parameter - Array of numbers inorder of size n2

Output Format

Return the TreeNode.

Example 1

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

Example 2

Input :
preorder = [10]
inorder = [10]
Output : 
[10]

Constraints:

• 1 <= preorder.length <= 3000
• inorder.length == preorder.length
• -3000 <= preorder[i], inorder[i] <= 3000
• preorder and inorder consist of unique values.
• Each value of inorder also appears in preorder.
• preorder is guaranteed to be the preorder traversal of the tree.
• inorder is guaranteed to be the inorder traversal of the tree.
• Expected Time Complexity: O(N)
• Expected Space Complexity: O(N)