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.

&nbsp;
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 = [-1], inorder = [-1]
Output: [-1]


&nbsp;
Constraints:


	1 &lt;= preorder.length &lt;= 3000
	inorder.length == preorder.length
	-3000 &lt;= preorder[i], inorder[i] &lt;= 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.


# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
    def buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        if not preorder or not inorder:
            return None

        root = TreeNode(preorder[0])
        mid = inorder.index(preorder[0])
        root.left = self.buildTree(preorder[1:mid+1], inorder[:mid])
        root.right = self.buildTree(preorder[mid+1:], inorder[mid+1:])
        return root
class Solution {
    Map<Integer, Integer> inMap;
    int curIndex = 0;
    int[] preOrder;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        preOrder = preorder;
        inMap = new HashMap<>();
        for(int i=0; i<inorder.length; i++) {
            inMap.put(inorder[i], i);
        }
        return dfs(0, preorder.length-1);
    }
    
    public TreeNode dfs(int s, int e){
        if(s > e) return null;
        int curNode = preOrder[curIndex++];
        TreeNode root  = new TreeNode(curNode);
        int inRoot = inMap.get(curNode);
        root.left = dfs(s, inRoot-1);
        root.right = dfs(inRoot+1, e);
        return root;
    }
}
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 * int val;
 * TreeNode *left;
 * TreeNode *right;
 * TreeNode() : val(0), left(nullptr), right(nullptr) {}
 * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    typedef vector<int>::iterator vecIt;

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder, TreeNode* retNode, vecIt startIt, vecIt endIt)
    {
        if (startIt >= endIt)
            return (NULL);
        vecIt rootIt;
        vecIt midIt;
        int rootVal;

        rootIt = preorder.begin();
        rootVal = *rootIt;
        preorder.erase(rootIt);
        retNode = new TreeNode(rootVal);
        midIt = find(startIt, endIt, rootVal);
        retNode->left = buildTree(preorder, inorder, retNode->left, startIt, midIt);
        retNode->right = buildTree(preorder, inorder, retNode->right, midIt + 1, endIt);
        return (retNode);
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        TreeNode* retNode;

        return (buildTree(preorder, inorder, retNode, inorder.begin(), inorder.end()));
    }
};
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 * this.val = (val===undefined ? 0 : val)
 * this.left = (left===undefined ? null : left)
 * this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = function(preorder, inorder) {
    let idx = 0;
    function create(inorderStart, inorderEnd) {
        if (idx === preorder.length || inorderStart > inorderEnd) {
            return null;
        }
        const root = new TreeNode(preorder[idx]);
        const mid = inorder.indexOf(preorder[idx]);
        idx++;
        root.left = create(inorderStart, mid -1);
        root.right = create(mid + 1, inorderEnd);
        return root;
    }

    return create(0, inorder.length -1);
};
Construct Binary Tree from Preorder and Inorder Traversal