A straightforward way -- O(n) time

• ``````//we pass the indices of post/inorder vector,
//which represents the begin and end of the sub tree
TreeNode* helper2( vector<int>& postorder, int poL, int poR,
vector<int>& inorder, int inL, int inR, map<int, int>& map)
{
if( poL > poR || inL > inR )
return NULL;
//everytime we insert the post order of sub tree's last element as root
TreeNode* root = new TreeNode( postorder[poR] );
int index = map[root->val];
//( index - inL ) means the length of the left subtree,
//we calculate the indices of the begin and end of the subtree in post/in order
root->left = helper2( postorder, poL, poL + ( index - inL ) - 1, inorder, inL, index-1, map );
root->right = helper2( postorder, poL+ ( index - inL ), poR-1, inorder, index+1, inR, map );
return root;

}

class Solution {
public:
TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {

if( postorder.size() == 0 || inorder.size() == 0 )
return NULL;
map<int, int> map;
//faster to get the indices and length of subtree
for( int i = 0; i < inorder.size(); i++ )
map[inorder[i]] = i;
return helper2(postorder,0,postorder.size()-1,inorder,0,inorder.size()-1, map);

}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.