I met this problem in MS interview and an additional request was

• 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;
}
};
``````

• Good luck for the interview.
your code is helpful and I modified my code with unordered_map assuming that maybe p or q is not in this tree.

• ``````# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def lowestCommonAncestor(self, root, p, q):
"""
:type root: TreeNode
:type p: TreeNode
:type q: TreeNode
:rtype: TreeNode
"""
self.result = None
# find p or q
def dfs(node, p, q):
if not node:
return node
left = dfs(node.left, p, q)
right = dfs(node.right, p, q)
if (left and right) or ((left or right) and (node == p or node == q)):
self.result = node
if node == p or node == q:
return node
return left if left else right
dfs(root, p, q)
return self.result
``````

I think a normal dfs and a global variable should work.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.