二叉搜索树最近公共祖先递归代码解析及递归逻辑疑问解答

嘿，我来帮你把这段递归代码的执行逻辑掰碎了说清楚！首先得记住二叉搜索树（BST）的核心性质：任意节点的左子树所有节点值都小于它，右子树所有节点值都大于它——这正是这段代码能高效找到LCA的关键。

先再贴一遍代码方便对照：

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

咱们就以你给出的树结构，找节点3和5的LCA为例，一步步走递归流程：

第一步：初始调用（root=6，p=3，q=5） #

先看第一个判断条件：p.val < root.val > q.val——也就是3 < 6 > 5，这个条件是成立的！因为3和5都比6小，说明p和q都在当前root的左子树里，所以递归调用lowestCommonAncestor(root.left, p, q)，也就是传入root=节点2，p=3，q=5。

第二步：递归调用（root=2，p=3，q=5） #

现在看第一个判断条件：3 < 2 >5？显然不成立。再看第二个判断条件：p.val > root.val < q.val——也就是3>2 <5，这个条件成立！因为3和5都比2大，说明p和q都在当前root的右子树里，所以递归调用lowestCommonAncestor(root.right, p, q)，传入root=节点4，p=3，q=5。

第三步：递归调用（root=4，p=3，q=5） #

现在看第一个判断条件：3 <4 >5？5比4大，不成立。第二个判断条件：3>4 <5？3比4小，也不成立。这时候两个if都不触发，直接执行return root，也就是返回节点4。

关键：返回值怎么传递回去？ #

你可能疑惑“root没被更新”怎么得到结果——其实递归的本质是栈调用，每个递归调用的返回值会被上一层调用接收并返回。比如：

• 第三步返回的节点4，会被第二步的递归调用接收，然后第二步的函数就把这个节点4返回给第一步的调用；
• 第一步的调用接收这个节点4，再把它作为初始调用的结果返回给你。

说白了，这段代码的逻辑是：

• 如果p和q都在当前root的左子树，就去左子树找；
• 如果都在右子树，就去右子树找；
• 当走到某个节点，p和q不在同一侧（一个左一个右），或者其中一个就是当前节点时，这个节点就是LCA，直接返回它。

这样就不用遍历整个树，完全利用BST的性质做定向搜索，效率特别高！

内容的提问来源于stack exchange，提问作者heretoinfinity