二叉搜索树查找最近目标值时出现比较失败问题求助

问题描述 #

我编写了一段Python代码，用于在二叉搜索树中查找最接近目标值的节点值。手动静态插入节点时代码运行正常，但使用array_to_bst方法生成树后执行报错。

相关代码 #

def clos(self,target):
    if self.root:
      self._clos(self.root,target)          

def _clos(self,curnode,value):
    a = curnode.val
    l=[]
    kid = curnode.left if value < a else curnode.right
    if not kid:
      return a
   
    else:
      b = self._clos(kid, value)
    l.extend([value-a,value-b])
    return min(map(abs,l))
    #print(l) for showing the None_object error
                    
tree = Tree()
l=[1, 2, 4, 5,7,13,15,22,70]
tree.array_to_bst(l)
print(tree.clos(3))

报错信息 #

Traceback (most recent call last):
  File "C:\Users\HP\Documents\Codes\new 1.py", line 110, in <module>
    print(tree.clos(3))
          ^^^^^^^^^^^^
  File "C:\Users\HP\Documents\Codes\new 1.py", line 91, in clos
    self._clos(self.root,target)          
    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "C:\Users\HP\Documents\Codes\new 1.py", line 102, in _clos
    l.extend([value-a,value-b])
                       ~~~~~~^~
TypeError: unsupported operand type(s) for -: 'int' and 'NoneType'

问题分析与修复 #

错误原因 #

1. clos方法未返回递归结果：clos函数调用_clos但没有返回其结果，导致递归返回值丢失，同时调用tree.clos(3)时实际获取的是None。
2. _clos函数逻辑错误：当前_clos返回的是差值的绝对值而非最接近目标值的节点值，导致上层递归中b接收的是差值而非节点值，后续计算value - b逻辑混乱，最终触发类型错误。

修复后的代码 #

def clos(self, target):
    if self.root:
        return self._clos(self.root, target)  
    # 树为空时可返回None或按需抛出异常
    return None

def _clos(self, curnode, value):
    # 初始最接近值设为当前节点值
    closest = curnode.val
    # 确定要遍历的子节点方向
    kid = curnode.left if value < closest else curnode.right
    
    if kid:
        # 递归获取子树中的最接近值
        child_closest = self._clos(kid, value)
        # 比较并保留更接近目标值的节点
        if abs(value - child_closest) < abs(value - closest):
            closest = child_closest
        elif abs(value - child_closest) == abs(value - closest):
            # 差值相同时，返回较小的节点值
            closest = min(closest, child_closest)
    
    return closest

修复说明 #

• clos方法新增return语句，确保递归结果能正确返回给调用者。
• _clos函数修改核心逻辑：始终返回节点值而非差值，每次递归时对比当前节点值与子树返回值，保留更接近目标的节点（差值相同时可选返回较小值），彻底避免类型错误和逻辑偏差。

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