# LeetCode Construct Binary Tree from Inorder and Postorder Traversal

LeetCode Construct Binary Tree from Inorder and Postorder Traversal

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

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

```class Solution {
private:
TreeNode* dfs(vector<int>& inorder, vector<int>& postorder, int inL, int inR, int postL, int postR, unordered_map<int, int>& hash) {
if (inL > inR || postL > postR)return NULL;
TreeNode* root = new TreeNode(postorder[postR]);
int idx = hash[root->val];
root->right = dfs(inorder, postorder, inL + 1, inR, postR - (inR - idx), postR - 1, hash);
root->left = dfs(inorder, postorder, inL, idx - 1, postL, postR - (inR - idx) - 1, hash);
return root;
}
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
if (inorder.size() == 0)return NULL;
unordered_map<int, int> hash;
for (int i = 0; i < inorder.size(); ++i) {
hash[inorder[i]] = i;
}
return dfs(inorder, postorder, 0, inorder.size() - 1, 0, postorder.size() - 1, hash);
}
};
```