/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:

    TreeNode* dfs(vector<int>& preorder, vector<int>& inorder, int pl, int pr, int il, int ir)
    {
        TreeNode* res = new TreeNode(preorder[pl]);
        if (pr == pl) return res;
        int idx = il;
        while (inorder[idx] != preorder[pl]) ++idx;
        int lengths = idx - il;
        if (idx > il)
            res->left = dfs(preorder, inorder, pl+1, pl+1+lengths-1, il, idx-1);
        if (idx < ir)
            res->right = dfs(preorder, inorder, pl+lengths+1, pr, idx+1, ir);
        return res;
    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (preorder.empty()) return NULL;
        return dfs(preorder, inorder, 0, preorder.size()-1, 0, inorder.size()-1);
    }
};