二叉搜索树递归查找异常求助：找到目标值仍提示未找到

嘿，我太懂你踩的这个坑了！递归查找二叉搜索树时最容易犯这个错——你明明在找到目标值的时候返回了True，但上层的递归调用没把这个返回值传递回去，结果导致程序最后还是走到了打印“未找到”的逻辑里，看起来就像返回值被“重置”了一样。

问题根源 #

先给你还原一下大概率出错的代码逻辑，应该是类似这样：

def bst_search(node, target):
    if node is None:
        return False
    if node.val == target:
        print(target)
        return True
    elif target < node.val:
        bst_search(node.left, target)  # 只调用递归，但没返回结果
    else:
        bst_search(node.right, target) # 同样没接住递归的返回值
    
    # 不管上面找没找到，都会走到这里，最后默认返回None，被判定为没找到
    print("未找到目标值")

当你在某个子节点匹配到目标值时，那个层级的递归确实返回了True，但上层调用只是执行了递归函数，并没有把这个True传递回去。上层递归会继续往下执行，最后走到打印“未找到”的代码，就出现了你看到的矛盾现象。

修复方案 #

核心就是每一层递归都要接住并返回子递归的结果，同时把“未找到”的提示放到真正确定没找到的场景（也就是遍历到空节点的时候）：

def bst_search(node, target):
    if node is None:
        print("未找到目标值")
        return False
    if node.val == target:
        print(target)
        return True
    elif target < node.val:
        # 接住左子树的查找结果，传递给上层调用
        return bst_search(node.left, target)
    else:
        # 接住右子树的查找结果，传递给上层调用
        return bst_search(node.right, target)

关键修复点 #

• 把“未找到”的打印逻辑移到递归终止条件（node is None）里，这样只有当遍历到树的尽头、确定没有目标值时才会触发提示
• 调用左/右子树的递归时，必须用return把结果传递回去，这样找到目标值的那个层级返回的True才能一路传递到最上层调用，不会丢失

这样修改后，只要找到目标值，递归会立刻把True逐层返回，不会走到打印“未找到”的逻辑；只有当遍历完所有可能的节点都没匹配到目标时，才会输出未找到的提示。

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