# Fast C++ solutions (recursive and iterative)

• Recursive solution with hashmap

``````class Solution {
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
unordered_map<int, int> map;
for (int i = 0; i < inorder.size(); ++i)
{
map[inorder[i]] = i;
}

return helper(0, postorder.size() - 1, 0, inorder.size() - 1, postorder, map);
}

TreeNode* helper(int poStart, int poEnd, int inStart, int inEnd, vector<int>& postorder, unordered_map<int, int>& map)
{
if (poStart > poEnd || inStart > inEnd)
{
return NULL;
}

int mid = postorder[poEnd];
TreeNode* root = new TreeNode(mid);
int inIndex = map[mid];

root->left = helper(poStart, poStart + inIndex - inStart - 1, inStart, inIndex - 1, postorder, map);
root->right = helper(poStart + inIndex - inStart, poEnd - 1, inIndex + 1, inEnd, postorder, map);

return root;
}

};
``````

Iterative solution with stack

``````class Solution {
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
if (inorder.empty())
{
return NULL;
}

TreeNode *dummy = new TreeNode(0x80000000);
stack<TreeNode*> nodeStack;
nodeStack.push(dummy);
TreeNode *prev = NULL, *curr = dummy;
int in = inorder.size() - 1, po = postorder.size() - 1;

while (in >= 0)
{
if (nodeStack.top()->val == inorder[in])
{
prev = nodeStack.top();
nodeStack.pop();
--in;
}
else if (prev)
{
curr = new TreeNode(postorder[po]);
prev->left = curr;
nodeStack.push(curr);
prev = NULL;
--po;
}
else
{
curr = new TreeNode(postorder[po]);
nodeStack.top()->right = curr;
nodeStack.push(curr);
--po;
}
}

curr = dummy->right;
delete dummy;

return curr;
}
};``````

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