二叉树节点查找函数找到目标却返回None类型的技术咨询

你遇到的这个问题其实是递归函数里很容易踩的坑——你在递归调用的时候没有把递归的结果返回出去！

咱们来拆解下你的代码问题：
当你要找的key大于当前root的key时，你调用了Find(key,root.right)，但这个调用的结果你并没有返回；同理，key小于当前root的key时，调用Find(key,root.left)后也没返回结果。只有当key完全匹配时，你才return了root，但如果目标节点是在递归的下层找到的，这个返回值根本不会传递到上层的调用函数里。上层函数执行完递归调用后，因为没有明确的return语句，就会默认返回None，最终最外层的调用拿到的就是None。

举个例子：假设目标节点在右子树的右子树里，最底层的递归找到节点后return了root，但它的上层调用只是执行了Find函数，没有把这个结果传回去，那上层函数就会走到函数末尾返回None，再往上的每一层都是如此，最终你拿到的temp就是None。

下面是修正后的代码，只需要在递归调用的地方加上return即可：

def Find(key, root):
    if root:
        if key > root.key:
            print("going right")
            return Find(key, root.right)  # 新增return，传递递归结果
        elif key < root.key:
            print("going left")
            return Find(key, root.left)   # 新增return，传递递归结果
        elif key == root.key:
            print("found")
            print(root)
            return root
    else:
        print("not in the tree")
        return 0  # 这里也可以考虑返回None，更符合查找失败的语义，看你的业务需求

现在再运行你的调用代码：

temp = Find(5, bt.root)
print(type(temp))

就能得到正确的<class '__main__.Node'>类型了，因为递归找到的节点会被逐层传递回最外层调用。

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