LeetCode 113. 路径总和 II — Python3 实现思路DFS 回溯从根节点深度优先遍历维护· path当前从根到当前节点的路径。· remaintargetSum 减去已走过路径的和。当到达叶子节点且 remain 0 时将 path 的副本加入结果。递归返回前把当前节点从 path 中弹出完成回溯。代码fromtypingimportOptional,List# Definition for a binary tree node.classTreeNode:def__init__(self,val0,leftNone,rightNone):self.valval self.leftleft self.rightrightclassSolution:defpathSum(self,root:Optional[TreeNode],targetSum:int)-List[List[int]]:res[]path[]defdfs(node:Optional[TreeNode],remain:int)-None:ifnotnode:returnpath.append(node.val)remain-node.val# 叶子节点且剩余和为 0ifnotnode.leftandnotnode.rightandremain0:res.append(path.copy())else:dfs(node.left,remain)dfs(node.right,remain)# 回溯path.pop()dfs(root,targetSum)returnres复杂度分析· 时间复杂度最坏 O(n²)。每个节点访问一次为 O(n)但找到合法路径时需复制 path代价为 O(h)链状树最坏 O(n²)平均接近 O(n)。· 空间复杂度O(h)递归栈深度与 path 长度均不超过树高 h结果集不计入。关键点叶子判断必须是 not node.left and not node.right否则非叶子节点可能因 remain 0 被误加。路径副本res.append(path.copy())不能直接 append(path)否则后续回溯会修改同一列表。回溯位置在递归左右子树后统一 path.pop()保证进入和离开节点时状态一致。剪枝本题节点值未限定正负不能根据 remain 0 提前返回。