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

基于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

Answer 2

我们可以计算目标节点数，如果它是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