在BST中最接近的位置

Question

我得到了迭代版本，但是以下递归代码始终返回None，我在哪里出错？在这里，我给出了迭代代码和递归代码的实现细节。

        def getClosestHelper(self,key: int, current_node: Node, closest_value) -> int: 
            if(current_node==None):
                return(closest_value)
            else:
                if(abs(key - current_node.value) < abs(key - closest_value)):
                    closest_value = current_node.value
                if(key < current_node.value):
                    self.getClosestHelper(key, current_node.left, closest_value)
                elif(key > current_node.value):
                    self.getClosestHelper(key, current_node.right, closest_value)
                else:
                    return(closest_value)

        def getClosest(self, key: int) -> int:
            return(self.getClosestHelper(key, self.root, float("inf")))

        """def getClosest(self, key: int) -> int:
            current_node = self.root
            closest_value = None
            difference = float("inf")
            while(current_node):
                current_difference = abs(key - current_node.value)
                if(current_difference < difference):
                    difference = current_difference
                    closest_value = current_node.value
                if(key < current_node.value):
                    current_node = current_node.left
                elif(key > current_node.value):
                    current_node = current_node.right
                else:
                    closest_value = current_node.value
                    break
            return(closest_value)"""


    if __name__ == '__main__':
        obj = B_S_T()
        obj.insertNode(Node(10))
        obj.insertNode(Node(5))
        obj.insertNode(Node(4))
        obj.insertNode(Node(6))
        obj.insertNode(Node(18))
        obj.insertNode(Node(13))
        obj.insertNode(Node(15))
        print(obj.getClosest(17))

Answer 1

尝试一下

def getClosestHelper(self,key: int, current_node: Node, closest_value) -> int: 
    if(current_node==None):
        return None
    else:
        if(abs(key - current_node.value) < abs(key - closest_value)):
            return current_node.value
        if(key < current_node.value):
            self.getClosestHelper(key, current_node.left, closest_value)
        elif(key > current_node.value):
            self.getClosestHelper(key, current_node.right, closest_value)

您不需要将值存储在closest_value中，只需将其返回即可。递归时，如果存储结果，则必须返回结果。