I met this problem in Microsoft interview. The interviewer required that maybe p or q is not in this tree, and in this case you should return nullptr.

The following is my solution. Is there a better solution ?

```
class Solution {
private:
struct Pair
{
int n;
TreeNode* node;
};
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
Pair t = helper(root, p, q);
if(t.n == 2)
{
return t.node;
}
return nullptr;
}
Pair helper(TreeNode* node, TreeNode* p, TreeNode* q)
{
Pair t = { 0, nullptr };
if(node == nullptr)
{
return t;
}
Pair l = helper(node->left, p, q);
Pair r = helper(node->right, p, q);
//t.n indicates the number of nodes we have found so far.
// t.node indicates the node we should return. It may be the ancestor, nullptr or pointer to p or q.
t.n = l.n + r.n + ((node == p || node == q) ? 1 : 0);
if(node == p || node == q || (l.n == 1 && r.n == 1))
{
t.node = node;
}
else
{
t.node = l.n >= 1 ? l.node : r.node;
}
return t;
}
};
```