递归查找二叉搜索树（BST）指定节点失败问题求助

核心错误原因 #

你的代码存在两个关键问题，导致除根节点外无法正确返回目标节点：

1. 递归返回值未传递：调用左/右子树递归后，没有接收或返回子树的查找结果。就算子树找到了目标节点，当前函数也会继续执行后续代码，最终返回None，导致结果无法传递到上层递归。
2. 全局变量冗余且无效：虽然你给全局变量nodeM赋值了目标节点，但上层递归函数并没有返回这个变量，最终调用者拿到的是最上层函数的return值（None）。

修正方案（纯递归返回值，无全局变量） #

这是递归查找的标准写法，直接通过返回值传递找到的节点：

def inorderTraversal(self, root: 'TreeNode', tval:int) -> 'TreeNode':
    if not root:
        return None
    
    # 先递归查找左子树，找到则直接返回结果
    left_node = self.inorderTraversal(root.left, tval)
    if left_node:
        return left_node
    
    # 检查当前节点是否是目标
    if root.val == tval:
        return root
    
    # 最后递归查找右子树，返回结果
    return self.inorderTraversal(root.right, tval)

更优方案（利用BST特性优化） #

因为是二叉搜索树（BST），可以利用其左子树节点值 < 根节点值 < 右子树节点值的特性，直接定向查找，不用遍历所有节点，效率更高：

def findBSTNode(self, root: 'TreeNode', tval:int) -> 'TreeNode':
    if not root:
        return None
    
    if root.val == tval:
        return root
    # 目标值更小，去左子树找
    elif tval < root.val:
        return self.findBSTNode(root.left, tval)
    # 目标值更大，去右子树找
    else:
        return self.findBSTNode(root.right, tval)

为什么原代码只对根节点有效？ #

当目标节点是根节点时，当前函数直接触发return nodeM，这个返回值会直接传递给调用者；但如果目标在子树里，子递归虽然找到了节点，但上层函数没有返回这个结果，最终还是会走到最后的return（返回None）。

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