我试图通过自顶向下的递归实现二叉树的最低公共祖先（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.
这也是StackOverflow上related questions的答案中的建议。
现在，如果我们假设树的所有节点都具有唯一的值，那么这段代码可以很好地工作。换言之，这种方法在出现重复的情况下似乎会中断（或者，这只是我的实现吗？）
我想知道如何修复我的代码，使其与重复的值一起工作。如果这种方法不能得到最优解，我应该如何改变我的方法？
具体实施如下：
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）
毫无疑问，根永远是祖先。
但是，存在一个“根”低于“根”的共同祖先。
最佳答案
你有一些问题：
1）为什么要检查node.val？您应该能够直接比较一个节点和另一个节点。当你有一个树有多个节点有相同的值时，这应该可以解决问题…假设这是你唯一的问题。
2）如果左子树非空，右子树非空，为什么要返回根？当然，在许多情况下，这将返回根这通常不是我们想要的行为。
你可能想从头开始重新思考你的算法（你有一些不错的想法，但是现在你发现你犯了一些错误，因为这个问题相当简单/直接，重新思考可能更有益）。
一个建议：由于这个问题是树上的问题，与搜索/路径有关，考虑从节点P到节点Q找到路径的问题。我们知道在树中，从任何两个节点中都存在一条路径（这是简单地从树是连接的非循环图的事实来定义的）。
当你在递归到一个基本情况之后，或者在递归到一个基本情况之后，你可能想创建一个数据结构来将访问过的节点存储在一个循环中，然后测试一些条件，可能会递归更多（本质上是dfs方法对bfs方法，而BFS方法使用显式的记忆/添加的内存，而DFS使用堆栈来记忆东西）。
关于python - 二叉树中使用递归的最低共同祖先，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/46452711/