Easy to Understand O(n) C++ Solution


#1

bool has( TreeNode* root,int key)
{
if (root == NULL)
return false;
queue<TreeNode*> q;
q.push(root);
while(q.size() != 0)
{
TreeNode* x = q.front();
q.pop();
if (x->val == key)
return true;
if (x->left != NULL) q.push(x->left);
if (x->right != NULL) q.push(x->right);
}
return false;
}
TreeNode* findLCA(TreeNode* root, int n1, int n2)
{
if (root == NULL) return NULL;
if (root->val == n1 || root->val == n2)
return root;

TreeNode *left_lca  = findLCA(root->left, n1, n2); 
TreeNode *right_lca = findLCA(root->right, n1, n2); 

if (left_lca && right_lca)  return root; 

return (left_lca != NULL)? left_lca: right_lca; 

}
int Solution::lca(TreeNode* A, int B, int C) {
if(has(A,B) && has(A,C))
return findLCA(A, B, C)->val;
return -1;
}