路径总和 II

🟡 Medium · 🏷️ 树、DFS、回溯、路径收集 · LeetCode#113

📖 题目

找出二叉树里所有从根到叶子、路径和等于 targetSum 的路径，返回这些路径本身（不是布尔值）。

输入	输出
`root=[5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum=22`	`[[5,4,11,2],[5,8,4,5]]`

💡 思路

这题是路径总和（判断存不存在）和二叉树的所有路径（收集所有路径）的结合：DFS 边走边记录路径，走到叶子节点判断路径和是否等于目标值，是就把整条路径收进结果。

257 那题路径存的是字符串，字符串不可变，path += x 天然不会串味。这题路径存的是 List[int]，列表是可变对象，直接用 path.append(x) 会导致左右子树共享同一个列表——处理完左子树的 append，右子树递归时看到的 path 也被污染了。有两种应对方式：

全局列表 + 回溯：append 进去，递归完子树后再 pop() 出来，手动恢复现场
每次传新列表：path = path + [node.val]——+ 会创建一个新列表，不修改原来那份，左右子树递归各拿各的，天然独立，不需要手动回溯，代价是每层都要复制一次列表

💻 代码

方法：传新列表（推荐，不易出错）

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        result = []

        def dfs(node: Optional[TreeNode], path: list, remain: int):
            if not node:
                return
            path = path + [node.val]           # 创建新列表，不影响调用者手里的那份
            if not node.left and not node.right:
                if node.val == remain:
                    result.append(path)
            else:
                dfs(node.left, path, remain - node.val)
                dfs(node.right, path, remain - node.val)

        dfs(root, [], targetSum)
        return result

时间复杂度 O(n × h)：每个节点访问一次，但每次 path + [x] 要复制一份长度约 h 的列表；空间复杂度跟递归栈和结果本身相关。换成"全局列表+回溯"能把时间降到 O(n)（append/pop 都是 O(1)），但要小心两处容易出错的地方：结果要用 path[:] 拷贝一份再存（不然存进去的是同一个引用，后面会被继续修改），递归完必须记得 pop() 撤销。