Hi,

I implemented you idea with Map, I wonder if you could tell me why it is O(n) complexity?

I think the space complexity of the recursion itself should be O(logn), the Map is O(n) space, so in total

the space complexity is O(n)
about the time complexity I am not sure, but I have read in this link that:

https://www.topcoder.com/community/data-science/data-science-tutorials/computational-complexity-section-2/

when the total work in each level is the same, we compute the work in each level, which is O(1) here, then we multiply it with number of levels which is O(logn) here, so is this the total time complexity O(logn)?

class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
Node* root;
for(int i=0; i<inorder.size(); ++i)
Map[inorder[i]]=i;
buildTree(root, 0, preorder.size()-1, preorder, 0, inorder.size()-1, inorder);
return root;
}
private:
void buildTree(Node* &root, int preS, int preE, const vector<int>& preorder,
int inS, int inE, const vector<int>& inorder) {
if(preS > preE) {
root=NULL;
return;
}
root=new TreeNode(preorder[preS]);
int index=Map[preorder[preS]];
buildTree(root->left, preS+1, preS+1+(index-inS-1), preorder, inS, index-1, inorder);
buildTree(root->right, preS+2+(index-inS-1), preE, preorder, index+1, inE, inorder);
}
unordered_map<int,int> Map;
};