题解 | #重建二叉树#

 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    map<int,int>mp;//记录中序遍历的位置，用空间换时间
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        for(int i=0;i<vin.size();i++){
            mp[vin[i]]=i;
        }
        return dfs(pre,vin,0,pre.size()-1,0,vin.size()-1);
    }
    TreeNode* dfs(vector<int> pre,vector<int> vin,int l1,int r1,int l2,int r2){
        if(l1>r1)return NULL;//当两区间中没有数字，说明遍历完了
        TreeNode* root=new TreeNode(pre[l1]);//创建根结点
        int mid=mp[pre[l1]]-l2;//相对根节点，记得减l2,容易错
        root->left=dfs(pre,vin,l1+1,l1+mid,l2,l2+mid-1);
        root->right=dfs(pre,vin,l1+mid+1,r1,l2+mid+1,r2);
        return root;
    }
};