题解 | #重建二叉树#

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    unordered_map<int, int> vin_rd;
public:
    TreeNode* reConstructBinaryTree(vector<int>& pre,vector<int>& vin) {
        if(pre.size() == 0){
            return nullptr;
        }
        
        for(int i=0; i<vin.size(); i++){
            vin_rd[vin[i]] = i;
        }
        
        return create(pre, vin, 0, pre.size()-1, 0, vin.size()-1);
    }
    
    TreeNode* create(vector<int>& pre,vector<int>& vin, int a, int b, int c, int d){
        if(a > b){
            return nullptr;
        }
        
        TreeNode* root = new TreeNode(0);
        root->val = pre[a];
        
        int index = vin_rd[pre[a]];
        root->left = create(pre, vin, a+1, a+index-c, c, index-1);
        root->right = create(pre, vin, a+index-c+1, b, index+1, d);
        return root;
    }
};