python - 使用递归的二叉树中的最低公共(public)祖先

Question

我正在尝试通过自上而下的递归来解决二叉树的最低公共(public)祖先(LCA)问题。

我使用的方法是:

IDEA: Find the node which has one of the desired nodes in either subtree while the other desired node is the opposite subtree.

PSEUDOCODE
1. If the value of root is equal to either of the desired node's value, 
   the root is the LCA.
2. Search in the left subtree for either node.
3. Search in the right subtree for either node.
4. If neither of them contains any of the two nodes,
   the nodes do not exist in the tree rooted at the root node.
5. If each of them contains one node,
   the root is the LCA.
6. If either one of them contains a node,
   return it to the root.

这也是 related questions 的答案中推荐的内容在 StackOverflow 上。
现在，如果我们假设树的所有节点都具有唯一值，则此代码可以很好地工作。换句话说，这种方法似乎在重复的情况下失效(或者，这只是我的实现吗？)

我想知道如何修复我的代码以处理重复值。如果这种方法不能得到最优解，我应该如何改变我的方法？

具体实现如下:

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

    def __repr__(self):
        return 'TreeNode({}, {}, {})'.format(self.val, self.left, self.right)

def lowestCommonAncestor(root, p, q):
    """
    :type root: TreeNode
    :type p: TreeNode
    :type q: TreeNode
    :rtype: TreeNode
    """
    if root is None:
        return None

    if p.val == root.val or q.val == root.val:
        return root

    left_subtree = lowestCommonAncestor(root.left, p, q)
    right_subtree = lowestCommonAncestor(root.right, p, q)

    if left_subtree is None and right_subtree is None:
        return None

    if left_subtree is not None and right_subtree is not None:
        return root

    if left_subtree is None:
        return right_subtree
    else:
        return left_subtree

例如:

root = TreeNode(2)
root.left = TreeNode(3)
root.left.left = TreeNode(1)
root.right = TreeNode(5)
root.right.left = TreeNode(7)
root.right.right = TreeNode(1)
print(lowestCommonAncestor(root, TreeNode(1), TreeNode(7)))

这将返回树的根作为结果。 结果 = 树节点(2)

毫无疑问，根永远是祖先。
但是，存在比根节点“低级”的共同祖先 - TreeNode(5)。

Answer 1

你有一些问题:1) 为什么要检查 Node.val？您应该能够直接将一个节点与另一个节点进行比较。当您有一棵具有多个具有相同值的节点的树时，这应该可以解决问题……假设这是您唯一的问题。

2) 如果左子树非空且右子树非空，为什么返回root？当然，在许多情况下，这将返回 root。这通常不是我们想要的行为。

您可能想从头开始重新考虑您的算法(您有一些不错的想法，但现在您发现自己犯了一些错误，并且由于这个问题相当简单/直接，重新思考可能更有益) .

一个建议:因为这个问题是关于树的问题，并且与搜索/路径有关，所以考虑寻找从节点 p 到节点 q 的路径的问题。我们知道，在一棵树中，任意两个节点都存在一条路径(根据定义，这只是因为树是连通无环图这一事实)。

在递归到基本情况后返回时，您可能会牢记这个想法，或者在递归到基本情况之后，您可能想要创建一个数据结构来存储循环中的访问节点，然后测试一些条件并可能递归更多(本质上是 DFS 方法与 BFS 方法，而 BFS 方法使用显式内存/添加内存，而 DFS 使用堆栈来记住东西)。