Python 如果不是二叉树中的所有这些节点，则查找二叉树中两个节点的最低共同祖先

Question

我明白了如果这两个节点必须在二叉树中如何解决，但是如果它们不必在树中怎么办？如果树中只有这些节点中的一个或none，return 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

Python 如果不是二叉树中的所有这些节点，则查找二叉树中两个节点的最低共同祖先

Python find lowest common ancestor of two nodes in a binary tree if not all of these nodes in the tree

python

tree

binary-tree