Python：递归创建列表的最佳方式？（附二叉树路径求和代码）

我写了一段用于二叉树路径求和的Python递归代码，通过递归动态向列表ans中添加子列表，但不确定这是不是最优的方式，想请教Python里递归创建列表的最优方法是什么？

我的代码如下：

# 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)

首先得指出你当前代码的几个小问题：依赖全局变量sum和ans会带来明显副作用——如果多次调用这个递归函数，ans里会残留之前的结果，而且全局变量也不利于代码的复用和单元测试。

递归创建列表的最优思路应该是让递归函数自身返回结果集合，而不是依赖外部的全局容器。这样代码更模块化、无副作用，也更符合函数式编程的干净风格。

针对你的二叉树路径求和场景，我们可以重构代码如下：

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

def find_path_sum(root, target_sum):
    # 递归辅助函数，返回当前节点开始的所有符合条件的路径
    def recurse(node, current_sum, current_path):
        if not node:
            return []
        
        # 更新当前路径和路径和（每次生成新列表，避免修改父调用的路径）
        new_sum = current_sum + node.val
        new_path = current_path + [node.val]
        
        # 如果是叶子节点，且路径和等于目标值，返回这个路径
        if not node.left and not node.right:
            return [new_path] if new_sum == target_sum else []
        
        # 递归遍历左右子树，合并两边的结果
        left_paths = recurse(node.left, new_sum, new_path)
        right_paths = recurse(node.right, new_sum, new_path)
        
        return left_paths + right_paths
    
    return recurse(root, 0, [])

# 使用示例
# 假设root是你的二叉树根节点
target = 25
result = find_path_sum(root, target)
print(result)

这个方案的优势很明显：

• 无全局变量：所有状态（当前路径、当前和）都通过递归参数传递，每次递归调用都是独立的，不会有残留数据的问题。
• 逻辑清晰：每个递归调用只负责返回自己子树中符合条件的路径，父调用只需要合并左右结果，分工明确。
• 易于复用：你可以多次调用find_path_sum，每次传入不同的根节点和目标值，结果都是完全独立的。

另外，你之前用tuple存储路径再转list的操作其实没必要，直接用list拼接（current_path + [node.val]）就可以——每次拼接都会生成新的列表，不会修改原来的路径，完美避免了递归中路径被意外污染的问题。

如果你的二叉树节点值都是非负数，还可以加个剪枝优化，减少不必要的递归调用：

def recurse(node, current_sum, current_path):
    if not node:
        return []
    
    new_sum = current_sum + node.val
    new_path = current_path + [node.val]
    
    # 节点值非负时，路径和超过目标就直接返回空，不用继续递归
    if new_sum > target_sum:
        return []
    
    if not node.left and not node.right:
        return [new_path] if new_sum == target_sum else []
    
    left_paths = recurse(node.left, new_sum, new_path)
    right_paths = recurse(node.right, new_sum, new_path)
    
    return left_paths + right_paths

总结一下，递归创建列表的最优方法核心就是：让递归函数返回子问题的结果，在父调用中合并这些结果，避免依赖外部状态，保持函数的纯功能性。

内容的提问来源于stack exchange，提问作者Jay Shri