Special topic of binary tree -- acwing 18 Rebuild the binary tree (construct the binary tree by traversing the front and middle order)

The idea and code are similar to the previous question AcWing 1497. Tree traversal , I won't go into too much detail here .

Code ：

class Solution {
    
public:
	#define map unordered_map
    map<int, int> d;
    vector<int> pre, in;


    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    
        pre = preorder, in = inorder;
        int n = inorder.size();
        for (int i = 0; i < n; ++i)
        {
    
            d[in[i]] = i;
        }
        return dfs(0, n - 1, 0, n - 1);
    }

    TreeNode* dfs(int pl, int pr, int il, int ir)
    {
    
        if (pl > pr) return nullptr;
        auto root = new TreeNode(pre[pl]);
        int k = d[root->val];
        TreeNode* le, * ri;
        le = dfs(pl + 1, k - il + pl, il, k - 1);
        ri = dfs(k - il + pl + 1, pr, k + 1, ir);
        root->left = le, root->right = ri;
        return root;
    }
};