<p>Given two integer arrays <code>preorder</code> and <code>inorder</code> where <code>preorder</code> is the preorder traversal of a binary tree and <code>inorder</code> is the inorder traversal of the same tree, construct and return <em>the binary tree</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/02/19/tree.jpg" style="width: 277px; height: 302px;" />
<pre>
<strong>Input:</strong> preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
<strong>Output:</strong> [3,9,20,null,null,15,7]
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> preorder = [-1], inorder = [-1]
<strong>Output:</strong> [-1]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= preorder.length &lt;= 3000</code></li>
	<li><code>inorder.length == preorder.length</code></li>
	<li><code>-3000 &lt;= preorder[i], inorder[i] &lt;= 3000</code></li>
	<li><code>preorder</code> and <code>inorder</code> consist of <strong>unique</strong> values.</li>
	<li>Each value of <code>inorder</code> also appears in <code>preorder</code>.</li>
	<li><code>preorder</code> is <strong>guaranteed</strong> to be the preorder traversal of the tree.</li>
	<li><code>inorder</code> is <strong>guaranteed</strong> to be the inorder traversal of the tree.</li>
</ul>

class Solution {
public:
    int search(vector<int> inorder,int start,int end,int curr){
        for(int i=start;i<=end;i++)
        {
            if(inorder[i]==curr)
            {
                return i;
            }
        }
        return -1;
    }
    TreeNode* helper(vector<int>&preorder,vector<int>&inorder,int start,int end,int& idx){
        if(start>end)
        {
            return nullptr;
        }
        int curr=preorder[idx];
        idx++;
        TreeNode* Node=new TreeNode(curr);
        if(start==end)
        {
            return Node;
        }
        int pos=search(inorder,start,end,curr);
        Node->left=helper(preorder,inorder,start,pos-1,idx);
        Node->right=helper(preorder,inorder,pos+1,end,idx);
        return Node;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) 
    {
        int idx=0;
        TreeNode* root=helper(preorder,inorder,0,inorder.size()-1,idx);
        return root;
    }
};
62124