1. /**
    2.  * Definition for a binary tree node.
    3.  * struct TreeNode {
    4.  *     int val;
    5.  *     TreeNode *left;
    6.  *     TreeNode *right;
    7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
    8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
    10.  * };
    11.  */
    12. class Solution {
    13. public:
    14.     unordered_map<int,int>index;
    15.     TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    16.         for(int i=0;i<inorder.size();i++){
    17.             index.emplace(inorder[i],i);
    18.         }
    19.         return builddfs(preorder,inorder,0,preorder.size()-1,0,preorder.size()-1);
    20.     }
    21.     TreeNode* builddfs(vector<int>& preorder, vector<int>& inorder,int preleft,int preright,int inleft,int inright){
    22.         if(preleft>preright){
    23.             return nullptr;
    24.         }
    25.         TreeNode* root=new TreeNode(preorder[preleft]);
    26.         int inroot=index[preorder[preleft]];
    27.         int dif=inroot-inleft;
    28.         root->left=builddfs(preorder,inorder,preleft+1,preleft+dif,inleft,inroot-1);
    29.         root->right=builddfs(preorder,inorder,preleft+dif+1,preright,inroot+1,inright);
    30.         return root;
    31.     }
    32. };