Python找到二叉树中两个节点的最低公共(public)祖先(如果不是树中的所有这些节点)

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