Python在二叉树中找到两个节点的最低公共祖先，如果不是树中的所有节点的话

Question

如果这两个节点必须在二进制树中，我知道如何解决这个问题，但如果它们不必在树中呢？如果树中只有一个或没有这些节点，则返回none。

这是我的代码：

# 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
        """
        [root,count] = self.findAncestor(root,p,q,0)
        if count == 2:
            return root
        else:
            return None
    def findAncestor(self,root,p,q,count):
        if not root:
            return None, count
        left,left_count = self.findAncestor(root.left, p, q,count)
        right,right_count = self.findAncestor(root.right,p,q,count)
        if root == p or root == q:
            return root,count+1
        if left and right:
            return root,count
        elif left:
            return left,left_count
        else:
            return right,right_count

但我总是得到错误的答案。有人知道如何根据我的代码修复它吗？谢谢

Answer 1

我们可以计算目标节点的数量，如果是2，那么我们知道两个节点都在树中。

class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        self.count = 0
        node = self.find(root, p, q)
        return node if self.count == 2 else None
    def find(self, node, p, q):
        if not node:
            return None
        if node in (p, q):
            self.count += 1
        left = self.find(node.left, p, q)
        right = self.find(node.right, p, q)
        return node if node in (p, q) or left and right else left or right

Answer 2

基于kitt的解决方案，我在lintCode问题578上测试了他的解决方案，但没有通过。该问题发生在计数条件下，该条件应与输入的两个节点再检查一次。因此，我重新设计了一个新的解决方案，它通过了lintcode测试，也具有更好的阅读逻辑。

"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        this.val = val
        this.left, this.right = None, None
"""

class Solution:
    """
    @param: root: The root of the binary tree.
    @param: A: A TreeNode
    @param: B: A TreeNode
    @return: Return the LCA of the two nodes.
    """
    count = 0
    def lowestCommonAncestor3(self, root, A, B):
        result = self.lca(root, A, B)
        return result if self.count == 2 else None
    def lca(self, root, A, B):
        if not root:
            return None
        for node in [A, B]:
            if root == node:
                self.count += 1
        left = self.lca(root.left, A, B)
        right = self.lca(root.right, A, B)
        if root in (A, B) or left and right:
            return root
        if left:
            return left
        if right:
            return right
        return None