二叉搜索树最近公共祖先(LCA)代码在大数据输入下运行失败排查

给定一棵二叉搜索树（BST），需找出树中两个指定节点的最近公共祖先（LCA）。根据维基百科定义：两个节点p和q的LCA是树中同时以二者为后代的最低节点（允许节点作为自身后代）。

基于BST特性，用两个队列分别记录根节点到p、q的路径，遍历队列找到首个分歧点，返回前一节点作为LCA。已知可通过BST逻辑优化，但需先排查当前代码问题。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
import collections
class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        queueForp = collections.deque()
        queueForq = collections.deque()
        phead = root
        qhead = root
        while phead != None:
            queueForp.append(phead)
            if phead == p:
                phead = None
            else:
                if phead.val < p.val:
                    phead = phead.right
                else:
                    phead = phead.left

        while qhead!= None:
            queueForq.append(qhead)
            if qhead == q:
                qhead = None
            else:
                if qhead.val < q.val:
                    qhead = qhead.right
                if qhead.val > q.val:
                    qhead = qhead.left
        print(queueForp)
        print(queueForq)
        prev = None
        while len(queueForp)!= 0 and len(queueForq) != 0:
            currp = queueForp.popleft()
            currq = queueForq.popleft()
            if currp.val == currq.val:
                prev = currp
            else:
                return prev
        
        return prev

代码在处理约10k规模的大型输入时失败，例如p=5893、q=3379时，输出为41，预期结果为5734，请求排查错误原因。

核心错误 #

构建q节点路径的循环中，第二个分支判断用了if而非elif，导致逻辑混乱：

• 当qhead.val < q.val时，代码会将qhead移到右子节点，但紧接着又执行if qhead.val > q.val的判断——此时qhead已经是新的右子节点，若该节点值大于q的val，会再次移到左子节点，直接偏离BST的正确搜索路径，最终记录的q路径完全错误。
• 而p节点的路径构建用了else，逻辑正确，这就导致两个路径对比时找到错误的公共节点。

修复代码 #

将q路径循环中的第二个if改为elif：

while qhead!= None:
    queueForq.append(qhead)
    if qhead == q:
        qhead = None
    else:
        if qhead.val < q.val:
            qhead = qhead.right
        elif qhead.val > q.val:  # 此处改为elif
            qhead = qhead.left

优化方案（可选） #

基于BST特性，无需记录完整路径即可找到LCA，空间复杂度为O(1)：

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

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