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 
15     unordered_map<int,int> hashMap; // key->节点值, value->中序遍历根节点位置
16     TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
17         int n = preorder.size();
18         for(int i = 0; i < n; i++)
19             hashMap[inorder[i]] = i; //记录中序遍历的根节点位置
20         return dfs(preorder,inorder,0,n-1,0,n-1);        
21     }
22     //pl,pr对应一棵子树的前序遍历区间的左右端点
23     //il,ir对应一棵子树的中序遍历区间的左右端点
24     TreeNode* dfs(vector<int>&pre,vector<int>&in,int pl,int pr,int il,int ir)
25     {
26         if(pl > pr || il > ir)  return NULL; //子树为空
27         int k = hashMap[pre[pl]] - il; // hashMap[pre[pl]]是中序遍历中根节点位置，k是子树前序和中序遍历的长度
28         TreeNode* root = new TreeNode(pre[pl]);
29         root->left = dfs(pre,in,pl+1,pl+k,il,il+k-1);  //左子树前序遍历，左子树中序遍历
30         root->right = dfs(pre,in,pl+k+1,pr,il+k+1,ir); //右子树前序遍历，右子树中序遍历
31         return root;
32     }