**You may have noticed that in most of my posts, I use methods totally different from others. (Of course, what's the point of repetition?)**

If we don't count the space occupied by the tree itself (otherwise what do we return?), then this solution is virtually O(1) space.

Unfortunately the test framework calls "delete" one by one on each node of the returned tree, which makes it impossible to preallocate the space of all nodes as a contiguous chunk.

```
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
uint e = inorder.size();
if (!e) return NULL;
uint n, k, p, o;
vector<TreeNode*> t(e);
for (uint i = 0; i < e; i++) {
t[i] = new TreeNode(inorder[i]);
}
for (uint i = 0; i < e; i++, p = n) {
for (n = 0; preorder[i] != inorder[n]; n++);
if (!i) o = p = n;
else if (n < p) t[p]->left = t[n];
else {
for (k = n - 1; k > p && !t[k]->left && !t[k]->right; k--);
t[k]->right = t[n];
}
}
return t[o];
}
};
```

If we are allowed to use extra space, then we can speed up with the help of "unordered_map".

*202 / 202 test cases passed.*

*Status: Accepted*

*Runtime: 15 ms*

```
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
uint e = inorder.size();
if (!e) return NULL;
uint n, k, p, o;
vector<TreeNode*> t(e);
unordered_map<int, uint> m;
for (uint i = 0; i < e; i++) {
t[i] = new TreeNode(inorder[i]);
m[inorder[i]] = i;
}
for (uint i = 0; i < e; i++, p = n) {
n = m[preorder[i]];
if (!i) o = p = n;
else if (n < p) t[p]->left = t[n];
else {
for (k = n - 1; k > p && !t[k]->left && !t[k]->right; k--);
t[k]->right = t[n];
}
}
return t[o];
}
};
```