Python二叉树搜索函数测试返回None，请求代码排查修正

题目原文 #

#One concept you will encounter in future CS class is the
#idea of a binary tree.
#
#A binary tree is made of nodes. Each node has three
#attributes: its own value, a left branch, and a right branch.
#The left branch will be lower than the node's own value, and
#the right branch will be higher than the node's own value.
#
#Some nodes will not have any branches; these are called leaf
#nodes. They only have their own value. Some nodes may have
#only one branch as well.
#
#Every binary tree has a single root node at the top of the
#tree. Most algorithms that operate on the tree will start at
#this root node.
#
#For example, let us imagine a binary tree with seven nodes.
#The top node's value is 10. The top node has two child nodes:
#the left node's value is 5, lower than 10. The right node's
#value is 15, higher than 10. Then, the left node has its own
#left and right nodes, with values 3 and 7: the lower and higher
#than 5 respectively, but both lower than 10 because they come
#from the original node's left (lower) branch. The right node's
#left and right branches have values 12 and 18, again lower
#and higher than 15 but both higher than 10.
#
#Below is the code for a single node. Right function called
#binary_tree_search. binary_tree_search should take two
#parameters: a single node, and a search value. It should return
#True if the search value is found anywhere in the tree with
#the node at the top, and False if the search value is not found.
#
#To do this, you'll want to write a function that goes down the
#tree similar to a binary search. If the search value is lower than
#the current node's value, it should continue searching to the
#left. If the search value is higher than the current node's value,
#it should continue searching to the right. If the search value is
#equal to the current node's value, it should return True. If the
#current node has no children (both left and right are None), it
#should return False as it has reached the bottom of the tree.
#
#You may assume that no two nodes will have the same value, and that
#every node will have either two children or none. You should not
#assume that the tree will have 7 nodes; it may have 3, 7, 15, 31,
#or more.
#
#HINT: Try breaking this into cases. What do you do if the node
#has the right value? What if the node is none? What if the node's
#value is higher than the search term? What if it's lower?
#
#HINT 2: To get around not knowing how big the tree will be,
#think about a process you can repeat over and over until either
#you find the search term or reach a leaf node. To repeat that
#process, you'd apply the same reasoning each time, just changing
#what node you're looking at.

class Node:
    def __init__(self, value, left = None, right = None):
        self.value = value
        self.left = left
        self.right = right

#Write your binary_tree_search function here!

我的代码 #

def binary_tree_search(node, node_value):
    #print(node.value)
    if node is None:
        return False
    elif node.value is node_value:
        return True
    elif node_value < node.value:
        #print("This is the left node: ", node.left.value)
        binary_tree_search(node.left, node_value)
    elif node_value > node.value:
        #print("This is the right node: ", node.right.value)
        binary_tree_search(node.right, node_value)
    else:
        return False

测试用例 #

#Below are some lines of code that will test your function.
#You can change the value of the variable(s) to test your
#function with different inputs.
#
#If your function works correctly, this will originally
#print: True, True, True, True, False, False, False
#(each on a separate line)

root_node = Node(10)
root_node.left = Node(5)
root_node.right = Node(15)
root_node.left.left = Node(3)
root_node.left.right = Node(7)
root_node.right.left = Node(12)
root_node.right.right = Node(18)

print(binary_tree_search(root_node, 18))
print(binary_tree_search(root_node, 7))
print(binary_tree_search(root_node, 15))
print(binary_tree_search(root_node, 10))
print(binary_tree_search(root_node, 1))
print(binary_tree_search(root_node, 11))
print(binary_tree_search(root_node, 21))

预期结果 #

True
True
True
True
False
False
False

实际结果 #

None
None
None
True
None
None
None

问题分析与修复 #

你的代码核心问题出在递归调用时没有返回递归结果：

• 当搜索值小于当前节点值时，你调用了binary_tree_search(node.left, node_value)，但没有用return把这个递归调用的结果传递回去；
• 同理，搜索值大于当前节点值时的递归调用也没有返回结果。

这就导致递归深入后找到结果（True/False），但无法传递到上层函数，最终除了根节点匹配的情况，其他场景函数都会因为没有明确返回值而默认返回None。

修复后的代码只需在递归调用前加上return，同时建议用==替代is判断值相等（is判断对象同一性，==才是判断值相等，更通用）：

def binary_tree_search(node, node_value):
    if node is None:
        return False
    elif node.value == node_value:
        return True
    elif node_value < node.value:
        return binary_tree_search(node.left, node_value)
    elif node_value > node.value:
        return binary_tree_search(node.right, node_value)
    else:
        return False

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