LeetCode 235题本地运行正常但提交失败，求问题排查

问题背景 #

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

本地测试代码 #

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

root = TreeNode(6)
root.left = TreeNode(2)
root.right = TreeNode(8)
root.left.left = TreeNode(0)
root.left.right = TreeNode(4)
root.left.right.left = TreeNode(3)
root.left.right.right = TreeNode(5)
root.right.left = TreeNode(7)
root.right.right = TreeNode(9)

p = 2
q = 8

class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
      
      def pathFind(path, node, target):

        path.append(node)
        if node.val == target:
            return path
        elif node.val < target:
            return pathFind(path, node.right, target)
        elif node.val > target:
            return pathFind(path, node.left, target)
        else:
            return None

      path_p = pathFind([], root, p) 
      path_q = pathFind([], root, q)

      idx = 0
      while True:

        if path_p[idx] == path_q[idx]:
          idx += 1
        else:
          break

      return path_p[idx - 1]

print(Solution().lowestCommonAncestor(root, p, q))

提交到LeetCode的代码 #

class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
      
      def pathFind(path, node, target):

        path.append(node)
        if node.val == target:
            return path
        elif node.val < target:
            return pathFind(path, node.right, target)
        elif node.val > target:
            return pathFind(path, node.left, target)
        else:
            return None

      path_p = pathFind([], root, p) 
      path_q = pathFind([], root, q)

      idx = 0
      while True:

        if path_p[idx] == path_q[idx]:
          idx += 1
        else:
          break

      return path_p[idx - 1]

问题根源 #

你忽略了LeetCode题目参数的类型差异：

• 本地测试时，你传入的p和q是数值（比如2、8），所以代码里用node.val == target能匹配到对应节点。
• 但LeetCode实际调用时，传入的p和q是TreeNode对象实例，不是数值。这会导致两个问题：
  1. node.val == target变成了“节点值和TreeNode对象比较”，永远不会相等，pathFind函数会一直递归直到空节点，最终返回None，引发后续报错。
  2. node.val < target这种比较会直接抛出类型错误，因为整数和TreeNode对象无法比较大小。

修正方案 #

直接针对TreeNode对象进行判断和比较，同时修复循环越界问题：

class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
      
      def pathFind(path, node, target):
        path.append(node)
        # 直接比较节点对象，而非值
        if node == target:
            return path
        # 用目标节点的val判断遍历方向
        elif node.val < target.val:
            return pathFind(path, node.right, target)
        elif node.val > target.val:
            return pathFind(path, node.left, target)
        else:
            return None

      path_p = pathFind([], root, p) 
      path_q = pathFind([], root, q)

      idx = 0
      # 增加索引边界判断，避免越界报错
      while idx < len(path_p) and idx < len(path_q):
        if path_p[idx] == path_q[idx]:
          idx += 1
        else:
          break

      return path_p[idx - 1]

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