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

 /*
 总体思路：就像人去模拟一样，首先找到一个根节点，再用findSubRoot函数去找这个
 根节点的左右儿子，然后将当前根节点的两个指针指向左右儿子
 再递归处理左右儿子
 */
class Solution {
public:
    static const int N = 1e3 + 11;
    int a[N], b[N], n;
    unordered_map<int, int> idx;

    //findSubTree用来寻找中序序列中l，r范围内哪个是根节点
    int findSubRoot(int l, int r){
        unordered_set<int> st;
        for(int i = l; i <= r; i++) st.insert(a[i]); //先将该范围内的数放到unordered_set里
        for(int i = 0;i < n; i++) if(st.count(b[i])) return b[i]; //从左到右第一个在前序中出现的
                                                                  //数即是根节点，返回它
        return -1;
    }

    //处理当前的根节点需要的参数分别是
    //根节点指针root，根节点在中序序列中的下标rootidx，左右子树在中序中索引的左右边界bl，br
    void dfs(TreeNode* root, int rootidx, int bl, int br){
        if(bl > br) return ;
        int subl = findSubRoot(bl, rootidx - 1);//左子树的根节点
        int subr = findSubRoot(rootidx + 1, br);//右子树的根节点
        if(subl != -1) root->left = new TreeNode(subl);
        if(subr != -1) root->right = new TreeNode(subr);
        dfs(root->left, idx[subl], bl, rootidx - 1);
        dfs(root->right, idx[subr], rootidx + 1, br);

    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        n = inorder.size();
        if(!n) return NULL;
        for(int i = 0;i < n; i++) b[i] = preorder[i];
        for(int i = 0;i < n; i++) {
            a[i] = inorder[i];
            idx[a[i]] = i;
        }
        TreeNode* root = new TreeNode(b[0]);
        dfs(root, idx[b[0]], 0, n - 1);
        return root;
    }
};