如何从python中的递归函数返回值？

Question

我在python中使用二叉树.我需要创建一个方法来搜索树并返回可以插入新值的最佳节点.但是我从这个递归函数返回一个值时遇到了麻烦.我是python的新手.

def return_key(self, val, node):
    if(val < node.v):
        if(node.l != None):
            self.return_key(val, node.l)
        else:
            print node.v
            return node
    else:
        if(node.r != None):
            #print node.v
            self.return_key(val, node.r)
        else:
            print node.v
            return node

打印node.v打印节点值,但是当我打印返回的节点时:

print ((tree.return_key(6, tree.getRoot().v)))

它打印

没有

结果.

Answer 1

您需要返回递归调用的结果.你在这里忽略它:

if(node.l != None):
    self.return_key(val, node.l)

和

if(node.r != None):
    self.return_key(val, node.r)

递归调用与其他函数调用没有什么不同,如果有的话,仍然需要处理返回值.使用return声明:

if(node.l != None):
    return self.return_key(val, node.l)

# ...

if(node.r != None):
    return self.return_key(val, node.r)

请注意,由于None是一个单例值,您可以而且应该is not None在这里测试缺席:

if node.l is not None:
    return self.return_key(val, node.l)

# ...

if node.r is not None:
    return self.return_key(val, node.r)

但是我怀疑你是否正在通过错误的参数来开始调用; 如果第二个参数是一个节点,请不要传递节点值:

print(tree.return_key(6, tree.getRoot())) # drop the .v

此外,如果你的所有node类都有相同的方法,你可以递归到那个而不是使用self.return_value(); 上Tree只是做:

print tree.return_key(6)

其中Tree.return_key()代表根节点:

def return_key(self, val):
    root = tree.getRoot()
    if root is not None:
        return tree.getRoot().return_key(val)

并Node.return_key()成为:

def return_key(self, val):
    if val < self.v:
        if self.l is not None:
            return self.l.return_key(val)
    elif val > self.v:
        if self.r is not None:
            return self.r.return_key(val)

    # val == self.v or child node is None
    return self

我val也在这里更新了测试逻辑; 如果val < self.v(或val < node.v在你的代码中)是假的,不要认为这val > self.v是真的; val可能是平等的.