/**

• 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:
  TreeNode buildTree(vector& preordertraversal, vector& inordertraversal)
  {

   unordered_map<int, size_t> inordertraversal_entry_index_map;
   
   for (size_t j = 0; j < inordertraversal.size(); ++j)
   {
       inordertraversal_entry_index_map.emplace(inordertraversal[j], j);
   }
   
   return Reconstruct_PreOrder_InOrder_Assistant(preordertraversal, 0, preordertraversal.size(), inordertraversal, 0, inordertraversal.size(), inordertraversal_entry_index_map);
   

  }

  // Assits the buildTree() to reconstruct the BST from pre[preorder_start : preorder_end - 1] and inorder[inorder_start : inorder_end - 1].

TreeNode *Reconstruct_PreOrder_InOrder_Assistant(const vector& preorder, size_t preorder_start, size_t preorder_end, const vector& inorder, size_t inorder_start, size_t inorder_end, const unordered_map<int, size_t>& in_entry_idx_map)

{
    if (preorder_start == preorder_end || inorder_start == inorder_end)
    {
        return nullptr;
    }

    auto idx = in_entry_idx_map.at(preorder[preorder_start]);
    
    auto left_tree_size = idx - inorder_start;

    auto node = new TreeNode(preorder[preorder_start]);
    
    node->left = Reconstruct_PreOrder_InOrder_Assistant(preorder, preorder_start + 1, preorder_start + 1 + left_tree_size, inorder, inorder_start, idx, in_entry_idx_map);
    
    node->right = Reconstruct_PreOrder_InOrder_Assistant(preorder, preorder_start + 1 + left_tree_size, preorder_end, inorder, idx + 1, inorder_end, in_entry_idx_map);
    
    return node;
    
}

};