Solution with O(n) space complexity


#1

void inorder(TreeNode* A,unordered_map<int,int> &map,int &i){
if(A==NULL)
return;
inorder(A->left,map,i);
map.insert(make_pair(A->val,i));
i++;
inorder(A->right,map,i);
}

int find(TreeNode* A,int B,int C,unordered_map<int,int> map){
if(A==NULL)
return -1;
if(map[B]<=map[A->val] && map[C]>=map[A->val])
return A->val;
else if(map[B]>=map[A->val] && map[C]<=map[A->val])
return A->val;
else if(map[B]<map[A->val] && map[C]<map[A->val])
return find(A->left,B,C,map);
else
return find(A->right,B,C,map);
}

int Solution::lca(TreeNode* A, int B, int C) {
unordered_map<int,int> map;
int i=0;
inorder(A,map,i);
if(map.find(B)==map.end())
return -1;
if(map.findĀ©==map.end())
return -1;
return find(A,B,C,map);
}