基于递归的二叉树最低公共祖先

Question

我试图通过自顶向下递归实现二叉树最低公共祖先(LCA)问题的解决方案。

我使用的方法是：

想法：找到在任一子树中有一个所需节点的节点，而另一个所需节点是相反的子树。

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.

以下是确切的实现：

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)))

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

Answer 1

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

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

您可能希望从头开始重新思考您的算法（您有一些不错的想法，但现在您看到您犯了一些错误，并且由于这个问题相当简单/直接，重新思考可能更有好处）。

建议：由于这个问题是一个树上的问题，并且与搜索/路径有关，所以考虑寻找从节点p到节点Q的路径的问题。我们知道，在一棵树中，任意两个节点都有一条路径（根据定义，这只是从树是一个连通的无环图这一事实中得出的）。

在返回到基本情况之后，或者在返回到基本情况之后，您可能希望创建一个数据结构来在循环中存储被访问的节点，然后测试一些条件，并可能递归更多（本质上是DFS方法与BFS方法相比，而BFS方法使用显式记忆/添加内存，而DFS使用堆栈来记住事情）。