/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

 struct TreeNode* dfs(int* pre, int* in, int pl, int pr, int il, int ir){

     if(pl > pr) return NULL;

     struct TreeNode* root = (struct TreeNode *) malloc(sizeof(struct TreeNode));
     root->val = pre[pl];

     int idx = 0;
     for(idx = il; idx < ir; idx ++){
         if(in[idx] == root->val) break;
     }
     int k = idx - il;
     root->left = dfs(pre, in, pl + 1, pl + k, il, il + k - 1);
     root->right = dfs(pre, in, pl + k + 1, pr, il + k + 1, ir);

     return root;
 }


struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize){

    if(!preorderSize || !inorderSize) return NULL;

    return dfs(preorder, inorder, 0, preorderSize-1, 0, preorderSize - 1);
}