1. /**
    2.  * Definition for a binary tree node.
    3.  * struct TreeNode {
    4.  *     int val;
    5.  *     TreeNode *left;
    6.  *     TreeNode *right;
    7.  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    8.  * };
    9.  */
    10. class Solution {
    11.     map<int,int> mp;
    12.     TreeNode* dfs(vector<int>& preorder, int pl, int pr, vector<int>& inorder, int il, int ir)
    13.     {
    14.         if(pr < pl) return nullptr;
    15.         TreeNode* root = new TreeNode(preorder[pl]);
    16.         int leftlen = mp[preorder[pl]] - il;//
    17.         int rightlen = ir - mp[preorder[pl]];
    18.         root->left = dfs(preorder, pl + 1, pl + leftlen, inorder, il, mp[preorder[pl]] - 1);
    19.         root->right = dfs(preorder, pl + leftlen + 1, pr, inorder, mp[preorder[pl]] + 1, ir);
    20.         return root;
    21.     }
    22. public:
    23.     TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    24.         for(int i = 0; i < inorder.size(); i++)
    25.             mp[inorder[i]] = i;
    26.         return dfs(preorder,0, preorder.size() - 1,inorder, 0, inorder.size() - 1);
    27.     }
    28. };

    第二次写题

    1. /**
    2.  * Definition for a binary tree node.
    3.  * struct TreeNode {
    4.  *     int val;
    5.  *     TreeNode *left;
    6.  *     TreeNode *right;
    7.  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    8.  * };
    9.  */
    10. class Solution {
    11.     map<int, int> mp; //val pos
    12.     TreeNode* dfs(vector<int>& preorder, int ps, int pe, vector<int>& inorder, int is, int ie)
    13.     {
    14.         if(ps > pe) return nullptr;
    15.         TreeNode* root = new TreeNode(preorder[ps]);
    16.         // cout << preorder[ps] << endl;;
    17.         int mid = mp[preorder[ps]];
    18.         int leftlen = mid - is;
    19.         int rightlen = ie - mid;
    20.         root->left = dfs(preorder, ps + 1, ps + 1 + leftlen - 1, inorder, is, mid - 1);
    21.         root->right = dfs(preorder, ps + leftlen + 1, pe, inorder, mid + 1, ie);
    22.         return root;
    23.     }
    24. public:
    25.     TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { 
    26.         for(int i = 0; i < inorder.size(); i++)
    27.             mp[inorder[i]] = i;
    28.         return dfs(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
    29.     }
    30. };