# 20ms c++ recursion solution

• Use a hash map to speed up the linear search of the index of root in "inorder", which, in the worst case, may take O(n^2) time.

``````   class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
if(preorder.size() == 0)
return nullptr;
unordered_map<int, int> inorder_map;
for(size_t i = 0; i < inorder.size(); ++i) {
inorder_map[inorder[i]] = i;
}
return buildTreeHelper(preorder, inorder, inorder_map, 0, preorder.size(), 0, inorder.size());
}

TreeNode* buildTreeHelper(vector<int>& preorder, vector<int>& inorder, unordered_map<int, int>& inorder_map,
size_t pstart, size_t pend, size_t istart, size_t iend) {
if(pend == pstart) {
return nullptr;
}

size_t i = inorder_map[preorder[pstart]];

TreeNode* node = new TreeNode(preorder[pstart]);
node->left = buildTreeHelper(preorder, inorder, inorder_map,
pstart + 1, pstart + 1 + i - istart, istart, i);
node->right = buildTreeHelper(preorder, inorder, inorder_map,
pstart + 1 + i - istart, pend, i + 1, iend);
return node;

}
};``````

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