Python递归创建列表的最佳方法是什么？

Question

# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None      

sum = 25
  ans = []
  def recurse(s, traverse, ls):
                #append tuple
                ls = ls + (traverse.val,)
                if (traverse.right):
                    recurse(s, traverse.right, ls)
                if (traverse.left):
                    recurse(s, traverse.left, ls)
                if (s==sum): 
                    #convert touple and add to answer
                    tmp = list(ls)
                    ans.append(tmp)

  a = tuple()
  recurse(0, root, a)

在这段代码中，我动态地将列表附加到一个列表（ans）中。在这个例子中，我使用递归和元组来构建每个子列表，因为它是不可变的。然后，我将其转换为一个列表，并将其附加到我的答案中。如果我只使用列表，我将无法在每次调用函数时传递副本。你知道吗

以这种方式使用元组是否有性能方面的缺点？有没有更好的方法来递归地创建类似问题的列表？你知道吗

而且，这种方法不适用于二维列表。。。制作2D不变列表的最佳方法是什么？你知道吗

Answer 1

我猜sum是您希望执行的最大遍历次数。你知道吗

以下操作将完成：

def traverse(root, limit=None, count=0):
    if not root or count == limit:
        return []
    traversal = [root.val]
    traversal += traverse(root.right, limit, count + len(traversal))
    traversal += traverse(root.left, limit, count + len(traversal))
    return traversal

那么，你就这样称呼它：

root = TreeNode(20)
root.right = TreeNode(40)
root.right.right = TreeNode(50)
root.right.left = TreeNode(30)
root.left = TreeNode(10)
root.left.left = TreeNode(5)

traverse(root)          // [20, 40, 50, 30, 10, 5]
traverse(root, limit=1) // [20]
traverse(root, limit=4) // [20, 40, 50, 30]

---

或者，如果您可以在__init__提供right和left节点，那么您可以采用一种很酷的函数式方法：

print(
    traverse(
        Node(20,
            right=Node(40,
                right=Node(50),
                left=Node(30)),
            left=Node(10,
                left=Node(5))),
        limit=3))
 # > [20, 40, 50]