深度优先搜索中list与list[:]的差异：LeetCode 113路径总和II解惑

问题背景 #

给定二叉树的根节点root和整数targetSum，返回所有从根到叶子节点的路径，路径上节点值之和等于targetSum，每条路径以节点值列表形式返回。根到叶子路径指从根出发到无子节点的叶子节点的路径。

最初采用深度优先搜索（DFS）实现的代码如下：

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        if root is None:
            return []   
        res = []
        path = []
        def dfs(node, path_sum):
            path_sum -= node.val
            path.append(node.val)
            if node.left is None and node.right is None:
                if path_sum == 0:
                    res.append(path)
                    
            if node.left is not None:
                dfs(node.left, path_sum)
            if node.right is not None:
                dfs(node.right, path_sum)
            
            path.pop()
        dfs(root, targetSum)
        return res

这段代码运行后返回的结果全是空列表，将res.append(path)改为res.append(path[:])后问题解决，请问背后的原因是什么？

原因解析 #

• Python中的列表是可变对象，执行res.append(path)时，只是把path列表的引用存入了res，而非创建一个新的列表副本。
• 你的DFS逻辑里，path会在递归回溯阶段不断执行pop()操作：找到符合条件的路径并添加到res后，后续的回溯步骤会逐步移除path中的元素，最终path会被清空。
• 由于res中所有元素都指向同一个path列表的引用，当path被清空后，res里的所有条目自然也变成了空列表。
• 而path[:]是对原列表进行浅拷贝，会生成一个包含当前path所有元素的新列表。将这个新列表添加到res后，后续对原path的修改不会影响到res中已保存的路径，从而能正确保留所有符合条件的路径。

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