LeetCode 235：二叉搜索树最近公共祖先代码返回None问题排查

我正在解决LeetCode 235. Lowest Common Ancestor of a Binary Search Tree问题，需要在给定二叉搜索树（BST）中找出两个指定节点的最近公共祖先（LCA）。我的代码如下：

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        ans = None

        def travel(root, p, q, ans):
            if not root: return
            temp=[]
            if root:
                temp.append(root.val)
            if root.right:
                temp.append(root.right.val)
            if root.left:
                temp.append(root.left.val)
            if p.val in temp and q.val in temp:
                ans = root
            if ans:
                return ans
            travel(root.left, p, q, ans)
            travel(root.right, p, q, ans)

        return travel(root, p, q, ans)

在测试用例 Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4 时，代码返回None，但在travel函数内尝试print(ans)时却能看到正确结果2。请问我的代码错误在哪里？

错误原因拆解 #

1. 变量作用域搞错了 #

你在外部函数定义的ans和内部travel函数里的ans是两个完全独立的变量。当你在travel里执行ans = root时，只是修改了函数内部的临时ans，外面的ans还是初始的None。所以哪怕你在travel内部print能看到正确值，外部的变量根本没被改动，最后返回的自然是None。

2. 递归返回值没处理 #

你递归调用travel(root.left, p, q, ans)的时候，就算左子树的递归已经找到了LCA节点，你也没接收这个返回值并向上传递。比如当左子树的travel返回了节点2，你直接忽略了这个结果，继续调用右子树的travel，最后整个travel函数没有把找到的节点返回出去，导致最终返回None。

3. LCA的判断逻辑不对 #

你用当前节点及其左右子节点的值组成列表，判断p和q的val是否在里面来确定LCA，这个逻辑不严谨。比如如果p和q都在当前节点的同一子树深处，你的逻辑会漏掉正确的LCA节点，而且完全没利用BST“左子树值全小于根，右子树值全大于根”的特性，既低效又容易出错。

修复方案 #

方案一：修正递归逻辑 #

用nonlocal关键字让内部函数能修改外部的ans，同时处理递归返回值：

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        ans = None

        def travel(node):
            nonlocal ans
            if not node or ans:  # 已经找到结果就直接返回，不用继续遍历
                return
            # 正确的LCA判断：当前节点是p/q，或者p和q分别在左右子树
            if (node.val == p.val or node.val == q.val) or \
               (p.val < node.val < q.val) or (q.val < node.val < p.val):
                ans = node
                return
            travel(node.left)
            travel(node.right)

        travel(root)
        return ans

方案二：利用BST特性优化（更高效） #

BST的有序性可以让我们直接定位LCA，不用遍历整个树：

• 如果p和q的值都比当前节点小，LCA肯定在左子树；
• 如果p和q的值都比当前节点大，LCA肯定在右子树；
• 剩下的情况（当前节点是p/q，或者p和q分别在左右），当前节点就是LCA。

递归版本：

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if p.val < root.val and q.val < root.val:
            return self.lowestCommonAncestor(root.left, p, q)
        elif p.val > root.val and q.val > root.val:
            return self.lowestCommonAncestor(root.right, p, q)
        else:
            return root

迭代版本（空间复杂度O(1)）：

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        while root:
            if p.val < root.val and q.val < root.val:
                root = root.left
            elif p.val > root.val and q.val > root.val:
                root = root.right
            else:
                return root
        return None

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