# LeetCode Construct Binary Tree from Preorder and Inorder Traversal

LeetCode Construct Binary Tree from Preorder and Inorder Traversal

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

```        3
/     \
9       20
/  \     /   \
1    2  15    17```
• 先序遍历结果为：3, 9, 1, 2, 20, 15, 17
• 中序遍历结果为：1, 9, 2, 3, 15, 20, 17

• 先序遍历结果为：3, 9, 1, 2, 20, 15, 17
• 中序遍历结果为：1, 9, 2, 3, 15, 20, 17

```class Solution {
private:
TreeNode* dfs(vector<int>& preorder, vector<int>& inorder, int preL, int preR, int inL, int inR, unordered_map<int, size_t>& hash) {
if (preL > preR || inL > inR)return NULL;
TreeNode* root = new TreeNode(preorder[preL]);
size_t idx = hash[root->val];
root->left = dfs(preorder, inorder, preL + 1, idx - inL + preL, inL, idx - 1, hash);
root->right = dfs(preorder, inorder, idx - inL + preL + 1, preR, idx + 1, inR, hash);
return root;
}

public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
if (preorder.size() == 0)return NULL;
unordered_map<int, size_t> hash;
for (size_t i = 0; i < inorder.size(); ++i) {
hash[inorder[i]] = i;
}
return dfs(preorder, inorder, 0, preorder.size() - 1, 0, inorder.size() - 1, hash);
}
};
```