我正在提高递归问题的能力。当问题陈述要求打印值时(例如,BST遍历,其中打印节点值),我没有任何问题;当问题要求返回值列表(例如,在树中返回两个节点之间的路径)时,我也没有太多问题。但是,如果有多个答案涉及到多个列表(或一个2D列表)需要返回时,我就会遇到问题。例如,问题要求我返回孩子可以达到楼梯顶部的方式数量,假设它可以一次跳1、2或3步。这不是问题,并且以下问题已经解决:
def step_helper(steps):
if(steps == 0):
return 1
elif(steps < 0):
return 0
else:
return step_helper(steps-1) +
step_helper(steps-2) +
step_helper(steps-3)
def find_num_ways(steps):
count = step_helper(steps)
print(count)
find_num_ways(10)
如果我需要从BST中返回两个节点之间的路径,那么返回一个列表就没有问题了。
def another_path_helper(self, n1, n2):
if(n1 == None):
return [None]
elif(n1 == n2):
return [n1.data]
elif(n1.data > n2.data):
return [n1.data] + self.another_path_helper(n1.left, n2)
elif(n1.data < n2.data):
return [n1.data] + self.another_path_helper(n1.right, n2)
else:
return None
def another_path(self, n1, n2):
path = self.another_path_helper(n1, n2)
if(None in path):
return None
else:
return path
然而,我不知道如何返回一个列表的列表。在子步骤示例中,如果我要返回孩子攀爬楼梯的方式数量,在不需要传递列表作为递归函数参数的情况下,如何返回路径列表(即二维列表),其中每个条目都是从底部到顶部所采取的步骤列表?理想情况下,我不需要将一个可变对象作为参数传递给我的递归函数,因为我被告知将可变对象传递给递归函数是一个不好的做法,与使用静态计数器没有什么区别。