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:
    map<int,int>pos;
    TreeNode* buildTree(vector<int>& pre, vector<int>& vin) {
        for(int i=0;i<(int)(vin.size());i++) pos[vin[i]] = i;
        auto root = dfs(0,pre.size()-1,0,vin.size()-1,pre,vin);
        return root;
    }
    TreeNode* dfs(int pl,int pr,int ml,int mr,vector<int>&pre,vector<int>& vin)
    {
        if(pl > pr || ml > mr) return nullptr;
        auto root = new TreeNode(pre[pl]);
        int k = pos[pre[pl]] - ml; //左子树的长度
        root->left = dfs(pl+1,pl+k,ml,ml+k-1,pre,vin);
        root->right = dfs(pl+k+1,pr,ml+k+1,mr,pre,vin);
        return root;
    }
};