TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
unordered_map<int, int> inorder_map;
// we need a map to look up the position of root in inorder, so
// that we can divide the tree into separate subtrees,
// reduces the complexity from n^2 to n assuming good hashing by unodered_map
for (int i = 0; i < inorder.size(); ++i) {
inorder_map[inorder[i]] = i;
}
return buildTreeHelper(postorder, 0, inorder.size()1, 0, postorder.size()1, inorder_map);
}
TreeNode* buildTreeHelper(vector<int>& post, int is, int ie, int ps, int pe, unordered_map<int, int>& inorder_map) {
if (is > ie  ps > pe) {
return NULL;
}
int root_val = post[pe];
TreeNode* root = new TreeNode(root_val);
int i = inorder_map.find(root_val)>second;
// number of nodes in left subtree
int l = iis;
root>left = buildTreeHelper(post, is, is+l1, ps, ps+l1, inorder_map);
root>right = buildTreeHelper(post, is+l+1, ie, ps+l, pe1, inorder_map);
return root;
}
O(n) c++ recursive solution  23ms with comments


Hi pankit,
Thanks for sharing your code.
In your code, the start point is is+l1/ps+l1 for inorder/postorder. I do not quite understand why we should calculate by using (start point + len  1) rather than (start point)? Becase l = iis, is+l1 = is+(iis)1 = i1.I tried to modify your code but it seemed incorrect for invalid inorder/postorder pairs like [1,3,2] and [3,2,1]. Any reason for that?