y总NB!

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
unordered_map<int,int> mp;
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        for(int i=0;i<(int)inorder.size();i++)
        {
            mp[inorder[i]]=i;
        }
        return dfs(0,preorder.size()-1,0,inorder.size()-1,preorder,inorder);
    }
    TreeNode* dfs(int pl,int pr,int il,int ir,vector<int>& preorder, vector<int>& inorder)
    {
        if(pl>pr) return NULL;
        int val = preorder[pl];
        int k = mp[val];
        int len = k-il;
        TreeNode* root = new TreeNode(val);
        root->left = dfs(pl+1,pl+len,il,k-1,preorder,inorder);
        root->right = dfs(pl+len+1,pr,k+1,ir,preorder,inorder);
        return root;
    }
};