从前序与中序遍历序列构造二叉树

该题主要是通过前序和中序遍历来还原一颗二叉树，核心的思路：在前序中找到根节点，根据该节点在中序遍历数组中的位置，根据中序划分左右子树，递归这个过程，还原一颗二叉树

本质上就是前序遍历中依次拿，不断地从中序遍历数组中缩小范围，范围为空的时候代表该范围拿不到了，需要换一颗子树。二叉树遍历的特点保证了前序遍历拿的元素一定可以在范围内找到

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

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        map<int, int> mp;
        for (int i = 0; i < inorder.size(); i++) {
            mp[inorder[i]] = i;
        }
        TreeNode* dummy = new TreeNode();

        int k = 0;
        auto dfs = [&](this auto&& dfs, int l, int r) -> TreeNode* {
            if (l > r) return NULL;
            TreeNode* root = new TreeNode(preorder[k++]);
            root->left = dfs(l, mp[root->val] - 1);
            root->right = dfs(mp[root->val] + 1, r);
            return root;
            };
        return dfs(0, preorder.size() - 1);
    }
};