/**
 * The run time complexity of this solution is O(n^2) in worse case. 
 *     As for each level, it need to search for the root node value in 
 *     inorder to determin the left/right tree divider
 *
 * However, we could build a map to mapping node value to its index in inorder
 *     array in O(n) time with O(n) space. Then we could find index of certain
 *     value in constant time, hence the time complexity could optimized to O(n)
 */


struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

/**
 * Build tree base on element of preorder in [i, j), and element iof inorder [m, n)
 * j-i == n-m
 */
TreeNode *buildTree(vector<int> &preorder, int i, int j, vector<int> &inorder, int m, int n) {
    if (j <= i) return NULL;
    
    int val = preorder[i];
    TreeNode *node = new TreeNode(val);

    int index = m;
    while(index < n && inorder[index] != val) ++index;

    if (index == n) {
        // this should be error if happen
        return NULL;
    }

    node->left = buildTree(preorder, i+1, index-m+i+1, inorder, m, index);
    node->right = buildTree(preorder, index-m+i+1, j, inorder, index+1, n);

    return node;
}

TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {

        buildTree(preorder, 0, preorder.size(), inorder, 0, inorder.size());
}