O(n) c++ recursive solution - 23ms with comments

• ``````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 = i-is;
root->left = buildTreeHelper(post, is, is+l-1, ps, ps+l-1, inorder_map);
root->right = buildTreeHelper(post, is+l+1, ie, ps+l, pe-1, inorder_map);

return root;
}``````

• Hi pankit,