Python:在二叉搜索树中寻找共同祖先的递归

Question

我一直在Leetcode的"讨论"选项卡中查看下面粘贴的代码，我觉得我不完全理解递归。 问题是关于在二叉搜索树中找到 2 个节点的共同祖先。

def lowestCommonAncestor(self, root, p, q):
if p.val < root.val > q.val:
return self.lowestCommonAncestor(root.left, p, q)
if p.val > root.val < q.val:
return self.lowestCommonAncestor(root.right, p, q)
return root

可以向我解释如何更改root以便在不更新其值的情况下给出答案吗？我看到root被传递到 main 函数中(像p和q这样的参数(，但递归调用只需要root.left和root.right。

你能用找到 3 和 5 的共同祖先的解释来澄清递归吗？

_______6______
/              
___2__          ___8__
/              /      
0      _4       7       9
/  
3   5

Stackoverflow在这里接受的答案使用递归，但没有回答我的问题。

我在哪里找到代码：https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/discuss/64963/3-lines-with-O(1(-space-1-linerers-Alternatives

Answer 1

你从树的根开始，p和q是你想要获得它们共同祖先的节点。

例如，当p是节点 3，q是节点 5 时。root为 6。

所以p.val < root.val > q.val会成立，现在你会打电话给self.lowestCommonAncestor(root.left, p, q). 您只是在函数之间移动对象的引用。

现在你的根将是2(根的左边(，p和q是一样的。现在，if p.val > root.val < q.val会成立，因为3 > 2和5 > 2，所以我们称self.lowestCommonAncestor(root.right, p, q).当我们把参数放在root.right，这只是对不同对象的引用。澄清一下，这不会更改任何对象的值，但会更改当前函数范围内的root值。

现在你的根将被4，并且没有任何条件会成立，所以你将返回4作为你的共同祖先。

Answer 2

这些if语句检查q和p在root方面是否在同一边。

首先if的意思：p和q都比根小，所以它们在左侧。所以，root不是他们的lowestCommonAncestor.例如，3和5在示例树中。他们属于这种情况。牠们都比6低，所以牠们的共同祖先在主树的左边。使用lowestCommonAncestor(root.left, p, q)继续执行下一步。

第二：与第一个相同，除了它们现在在右侧。它们都大于root，所以它们必须在root.right的某个地方有一个lowestCommonAncestor。

此功能一直持续到p和q不再在同一侧的情况。在这种情况下，root是lowestCommonAncestor。