题解 | #重建二叉树# 记下来，感觉没有真正理解

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    unordered_map<int, int>mp;
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        int len = pre.size();
        if (len == 0) {
            return nullptr;
        }
        for (int i = 0; i < len; i++) {
            mp[vin[i]] = i;
        }
        return dfs(pre, vin, 0, len - 1, 0, len - 1);
    }
    TreeNode * dfs(vector<int> pre,vector<int> vin, int preLeft, int preRight, int inLeft, int inRight) {
        if (preLeft > preRight || inLeft > inRight) {
            return nullptr;
        }
        // 获取pos
        int pos = mp[pre[preLeft]];
        TreeNode *root = new TreeNode(pre[preLeft]); // 左子树节点的个数为 pos - inLeft
        root->left = dfs(pre, vin, preLeft + 1, preLeft + pos - inLeft, inLeft, pos - 1); // 注意pre的左子树应该去掉首值
        root->right = dfs(pre, vin, preLeft + pos - inLeft + 1, preRight, pos + 1, inRight);
        return root;
    }
};