在问之前,我搜索了一些旧问题,得到了一个更好的想法,将“return”放在前面,里面重新调用了函数,得到了预期的结果。 其中一些喜欢: How to stop python recursion Python recursion and return statements .但是当我对我的问题做同样的事情时,情况会变得更糟。
我有一个二叉搜索树,想通过给定一个节点的键来获取 TreeNode 实例,所以它看起来更容易遍历需求,我已经很容易地实现了下面类似的功能,我没有在函数前面放 return :
#preorder_List=[]
def preorder(treeNode):
if treeNode:
preorder_List.append(treeNode.getKey())
preorder(treeNode.has_left_child())
preorder(treeNode.has_right_child())
return preorder_List
所以对于我的新需求,我首先将其编写如下:
def getNode(treeNode,key):
if(treeNode):
if(treeNode.key==key):
print("got it=",treeNode.key)
return treeNode
else:
getNode(treeNode.left_child(),key)
getNode(treeNode.right_child(),key)
然后问题出现了,它找到了键/节点但一直运行并最终报告一个None错误然后我将return放在左右分支的前面,如下所示:
def getNode(treeNode,key):
if(treeNode):
if(treeNode.key==key):
print("got it=",treeNode.key)
return treeNode
else:
return getNode(treeNode.left_child(),key)
return getNode(treeNode.right_child(),key)
但这让事情变得更糟,它确实到达了找到的键并更早地返回 None。
然后我尝试为分支删除一个“返回”,无论是右还是左。它有效(更新:当我的测试用例仅包含 3 个节点时,它有效,当我放置更多节点时,它不起作用,或者说预期的节点是否来自右侧,然后将 return 放在右侧分支调用之前,对于左边的,它没有)。什么是更好的解决方案?
请您参考如下方法:
您需要能够返回 递归调用的结果,但您并不总是需要无条件地这样做。有时您不会从第一个递归中获得所需的结果,因此您需要在返回任何内容之前对另一个递归进行递归。
处理此问题的最佳方法通常是将递归的结果分配给一个变量,然后您可以对其进行测试。因此,如果 getNode 要么返回一个节点(如果它找到了键),要么返回一个节点 None(如果它没有找到),你可以这样做:
result = getNode(treeNode.left_child(),key)
if result is not None:
return result
return getNode(treeNode.right_child(),key)
在这种特定情况下,由于 None 是错误的,您可以使用 或 运算符为您做“短路”:
return getNode(treeNode.left_child(),key) or getNode(treeNode.right_child(),key)
只有在第一个递归调用返回错误值(例如None)时才会进行第二次递归调用。
请注意,对于某些递归算法,您可能需要无条件递归多次,然后将结果组合在一起再返回。例如,将树中的(数字)键值相加的函数可能如下所示:
def sum_keys(node):
if node is None: # base case
return 0
left_sum = sumKeys(node.left_child()) # first recursion
right_sum = sumKeys(node.right_child()) # second recursion
return left_sum + right_sum + node.key # add recursive results to our key and return
