LeetCode-Book 精讲路径总和 IILeetCode 113——先序遍历 回溯记录根到叶路径的完整攻略【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book导读《路径总和 II》是二叉树路径类问题中的经典回溯题也是《Krahets 笔面试精选 88 题》题单中的高频考点。本文以 113. 路径总和 II.md 为骨架结合 LeetCode-Book 仓库中 Python、Java、C 三份可直接运行的实现与测试用例系统讲解「先序遍历 路径记录」的解题框架、递归回溯的每一步细节以及三种语言中路径拷贝的隐蔽坑位。读完本文你将掌握根到叶路径枚举类题目的标准回溯写法并能直接运行仓库代码验证结果。题目概述给定一棵二叉树的根节点root和一个整数目标和targetSum找出所有从根节点到叶子节点路径总和等于给定目标和的路径。路径必须从根节点出发、到叶子节点结束中间不能截断叶子节点没有子节点的节点输出所有满足条件的路径列表每条路径由节点值序列构成。例如仓库测试用例使用的二叉树[5, 4, 8, 11, None, 13, 4, 7, 2, None, None, 5, 1]、targetSum 22答案应为两条路径[5, 4, 11, 2]和[5, 8, 4, 5]。解题思路先序遍历 路径记录本题是典型的回溯Backtracking问题解法由两部分组成先序遍历按照「根、左、右」的顺序遍历树的所有节点保证每条路径都从根出发路径记录在遍历过程中维护从根节点到当前节点的路径当某条路径同时满足以下两个条件时将其加入结果列表该路径是根节点到叶子节点形成的完整路径该路径上所有节点值的和等于目标值targetSum。之所以采用先序遍历是因为路径天然具有「根 → 叶」的方向性先序恰好先访问父节点再访问子节点能在进入任意节点时立即获得从根到它的完整路径前缀无需额外存储祖先链。算法流程详解整个解法分为入口函数pathSum(root, targetSum)与递归函数recur(root, tar)两层。入口函数pathSum(root, targetSum)初始化结果列表res存放所有符合条件的路径、路径列表path记录当前探索路径启动递归以根节点和完整目标值targetSum调用recur返回值直接返回res。递归函数recur(root, tar)递推参数当前节点root当前目标值tar剩余需要凑齐的数值终止条件若root为空None/null/nullptr直接返回不做任何处理递推工作共 5 步路径更新将当前节点值root.val加入路径path目标值更新tar tar - root.val即让目标值从targetSum沿途递减至 0路径记录当root为叶子节点左右子节点均为空且tar 0时说明当前path是一条完整且合法的根到叶路径将其拷贝后加入res先序遍历分别递归左子节点recur(root.left, tar)与右子节点recur(root.right, tar)路径恢复回溯向上返回前将当前节点从path中删除即执行path.pop()/path.removeLast()/path.pop_back()。第 5 步是整个回溯法的精髓path是全程复用的「共享栈」递归深入时压入节点递归返回时弹出节点从而保证每一时刻path恰好等于当前搜索分支的路径空间开销被压到 O(树高)。三种语言实现与关键坑位路径必须拷贝记录路径时若直接执行res.append(path)加入res的是path对象本身引用后续回溯时path.pop()会改变同一对象的内容导致res中已记录的路径也被同步篡改最终结果错误。因此必须拷贝一份路径快照再存入resPythonres.append(list(path))——list(path)创建新列表Javares.add(new LinkedList(path))—— 以path为元素构造新链表Cres.push_back(path)——path按值拷贝入vector天然是深拷贝。三种写法原理一致避免把正在被回溯修改的path引用直接塞进结果集。Python 实现class Solution: def pathSum(self, root: Optional[TreeNode], targetSum: int) - List[List[int]]: res, path [], [] def recur(root, tar): if not root: return path.append(root.val) tar - root.val if tar 0 and not root.left and not root.right: res.append(list(path)) recur(root.left, tar) recur(root.right, tar) path.pop() recur(root, targetSum) return res仓库中可运行版本见 lc_113_path_sum_ii.py其中已内置测试用例list_to_tree([5, 4, 8, 11, None, 13, 4, 7, 2, None, None, 5, 1])targetSum 22运行后打印[[5, 4, 11, 2], [5, 8, 4, 5]]。Java 实现class Solution { LinkedListListInteger res new LinkedList(); LinkedListInteger path new LinkedList(); public ListListInteger pathSum(TreeNode root, int targetSum) { recur(root, targetSum); return res; } void recur(TreeNode root, int tar) { if (root null) return; path.add(root.val); tar - root.val; if (tar 0 root.left null root.right null) res.add(new LinkedListInteger(path)); recur(root.left, tar); recur(root.right, tar); path.removeLast(); } }仓库可运行版本见 lc_113_path_sum.java其main方法通过 TreeNode.arrToTree 将数组[5, 4, 8, 11, null, 13, 4, 7, 2, null, null, 5, 1]还原为二叉树并执行用例。C 实现class Solution { public: vectorvectorint pathSum(TreeNode* root, int targetSum) { recur(root, targetSum); return res; } private: vectorvectorint res; vectorint path; void recur(TreeNode* root, int tar) { if (root nullptr) return; path.push_back(root-val); tar - root-val; if (tar 0 root-left nullptr root-right nullptr) res.push_back(path); recur(root-left, tar); recur(root-right, tar); path.pop_back(); } };仓库可运行版本见 lc_113_path_sum_ii_s1.cpp。从仓库源码看测试用例的组织方式LeetCode-Book 为每题提供了「解法代码 测试用例 驱动代码」的完整骨架本题三份代码均遵循该模式Python测试用例直接写在题解文件底部调用 include/binary_tree.py 中的list_to_tree将层序数组还原为二叉树targetSum 22随后Solution().pathSum(...)并print结果Javamain方法中使用include包下 TreeNode.arrToTree 完成同样的数组 → 树转换C通过#include ../include/include.hpp引入 TreeNode.hpp 等公共头文件主函数预留了测试用例挂载点。从源码结构可以看出list_to_tree/arrToTree均采用**层序遍历队列**从数组构造二叉树null表示该位置无子节点其余整数按层序依次挂到父节点左右。这与本题递归回溯配合得当——树的构造与路径枚举彼此独立读者可以自由替换用例数组来验证不同形态的树。复杂度分析时间复杂度 O(N)N 为二叉树的节点数先序遍历需要访问所有节点每个节点仅进出path一次空间复杂度 O(N)最差情况下树退化为链表每层只有一个子节点此时递归深度与path长度均为 Npath存储全部节点递归调用栈也占用 O(N) 空间一般二叉树场景下递归深度与path长度等于树高空间为 O(log N)O(N)。变体与延伸掌握本题的回溯写法后可自然迁移到同族题目路径总和 I只需判断是否存在合法路径找到即返回无需维护path与结果集路径总和 III路径不必从根出发、也不必止于叶需要额外引入前缀和或双重递归二叉树的所有路径257不再要求路径和仅枚举全部根到叶路径是本题去掉求和约束后的退化版本。这些题共享「先序遍历维护路径、叶子处结算、回溯弹出节点」的核心模式区别只在于结算条件与路径起止约束。小结核心框架 先序遍历递归 路径记录回溯5 步递推流程缺一不可记录答案时必须拷贝路径Python 用list(path)、Java 用new LinkedList(path)、C 用push_back的值语义复杂度稳定为 O(N) 时间、O(N) 空间适合面试中手写并解释「为什么不能直接 append(path)」完整可运行代码与测试用例见 Python、Java、C 三份文件可直接本地运行对照验证。【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode-Book 精讲：路径总和 II（LeetCode 113）——先序遍历 + 回溯记录根到叶路径的完整攻略
LeetCode-Book 精讲路径总和 IILeetCode 113——先序遍历 回溯记录根到叶路径的完整攻略【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book导读《路径总和 II》是二叉树路径类问题中的经典回溯题也是《Krahets 笔面试精选 88 题》题单中的高频考点。本文以 113. 路径总和 II.md 为骨架结合 LeetCode-Book 仓库中 Python、Java、C 三份可直接运行的实现与测试用例系统讲解「先序遍历 路径记录」的解题框架、递归回溯的每一步细节以及三种语言中路径拷贝的隐蔽坑位。读完本文你将掌握根到叶路径枚举类题目的标准回溯写法并能直接运行仓库代码验证结果。题目概述给定一棵二叉树的根节点root和一个整数目标和targetSum找出所有从根节点到叶子节点路径总和等于给定目标和的路径。路径必须从根节点出发、到叶子节点结束中间不能截断叶子节点没有子节点的节点输出所有满足条件的路径列表每条路径由节点值序列构成。例如仓库测试用例使用的二叉树[5, 4, 8, 11, None, 13, 4, 7, 2, None, None, 5, 1]、targetSum 22答案应为两条路径[5, 4, 11, 2]和[5, 8, 4, 5]。解题思路先序遍历 路径记录本题是典型的回溯Backtracking问题解法由两部分组成先序遍历按照「根、左、右」的顺序遍历树的所有节点保证每条路径都从根出发路径记录在遍历过程中维护从根节点到当前节点的路径当某条路径同时满足以下两个条件时将其加入结果列表该路径是根节点到叶子节点形成的完整路径该路径上所有节点值的和等于目标值targetSum。之所以采用先序遍历是因为路径天然具有「根 → 叶」的方向性先序恰好先访问父节点再访问子节点能在进入任意节点时立即获得从根到它的完整路径前缀无需额外存储祖先链。算法流程详解整个解法分为入口函数pathSum(root, targetSum)与递归函数recur(root, tar)两层。入口函数pathSum(root, targetSum)初始化结果列表res存放所有符合条件的路径、路径列表path记录当前探索路径启动递归以根节点和完整目标值targetSum调用recur返回值直接返回res。递归函数recur(root, tar)递推参数当前节点root当前目标值tar剩余需要凑齐的数值终止条件若root为空None/null/nullptr直接返回不做任何处理递推工作共 5 步路径更新将当前节点值root.val加入路径path目标值更新tar tar - root.val即让目标值从targetSum沿途递减至 0路径记录当root为叶子节点左右子节点均为空且tar 0时说明当前path是一条完整且合法的根到叶路径将其拷贝后加入res先序遍历分别递归左子节点recur(root.left, tar)与右子节点recur(root.right, tar)路径恢复回溯向上返回前将当前节点从path中删除即执行path.pop()/path.removeLast()/path.pop_back()。第 5 步是整个回溯法的精髓path是全程复用的「共享栈」递归深入时压入节点递归返回时弹出节点从而保证每一时刻path恰好等于当前搜索分支的路径空间开销被压到 O(树高)。三种语言实现与关键坑位路径必须拷贝记录路径时若直接执行res.append(path)加入res的是path对象本身引用后续回溯时path.pop()会改变同一对象的内容导致res中已记录的路径也被同步篡改最终结果错误。因此必须拷贝一份路径快照再存入resPythonres.append(list(path))——list(path)创建新列表Javares.add(new LinkedList(path))—— 以path为元素构造新链表Cres.push_back(path)——path按值拷贝入vector天然是深拷贝。三种写法原理一致避免把正在被回溯修改的path引用直接塞进结果集。Python 实现class Solution: def pathSum(self, root: Optional[TreeNode], targetSum: int) - List[List[int]]: res, path [], [] def recur(root, tar): if not root: return path.append(root.val) tar - root.val if tar 0 and not root.left and not root.right: res.append(list(path)) recur(root.left, tar) recur(root.right, tar) path.pop() recur(root, targetSum) return res仓库中可运行版本见 lc_113_path_sum_ii.py其中已内置测试用例list_to_tree([5, 4, 8, 11, None, 13, 4, 7, 2, None, None, 5, 1])targetSum 22运行后打印[[5, 4, 11, 2], [5, 8, 4, 5]]。Java 实现class Solution { LinkedListListInteger res new LinkedList(); LinkedListInteger path new LinkedList(); public ListListInteger pathSum(TreeNode root, int targetSum) { recur(root, targetSum); return res; } void recur(TreeNode root, int tar) { if (root null) return; path.add(root.val); tar - root.val; if (tar 0 root.left null root.right null) res.add(new LinkedListInteger(path)); recur(root.left, tar); recur(root.right, tar); path.removeLast(); } }仓库可运行版本见 lc_113_path_sum.java其main方法通过 TreeNode.arrToTree 将数组[5, 4, 8, 11, null, 13, 4, 7, 2, null, null, 5, 1]还原为二叉树并执行用例。C 实现class Solution { public: vectorvectorint pathSum(TreeNode* root, int targetSum) { recur(root, targetSum); return res; } private: vectorvectorint res; vectorint path; void recur(TreeNode* root, int tar) { if (root nullptr) return; path.push_back(root-val); tar - root-val; if (tar 0 root-left nullptr root-right nullptr) res.push_back(path); recur(root-left, tar); recur(root-right, tar); path.pop_back(); } };仓库可运行版本见 lc_113_path_sum_ii_s1.cpp。从仓库源码看测试用例的组织方式LeetCode-Book 为每题提供了「解法代码 测试用例 驱动代码」的完整骨架本题三份代码均遵循该模式Python测试用例直接写在题解文件底部调用 include/binary_tree.py 中的list_to_tree将层序数组还原为二叉树targetSum 22随后Solution().pathSum(...)并print结果Javamain方法中使用include包下 TreeNode.arrToTree 完成同样的数组 → 树转换C通过#include ../include/include.hpp引入 TreeNode.hpp 等公共头文件主函数预留了测试用例挂载点。从源码结构可以看出list_to_tree/arrToTree均采用**层序遍历队列**从数组构造二叉树null表示该位置无子节点其余整数按层序依次挂到父节点左右。这与本题递归回溯配合得当——树的构造与路径枚举彼此独立读者可以自由替换用例数组来验证不同形态的树。复杂度分析时间复杂度 O(N)N 为二叉树的节点数先序遍历需要访问所有节点每个节点仅进出path一次空间复杂度 O(N)最差情况下树退化为链表每层只有一个子节点此时递归深度与path长度均为 Npath存储全部节点递归调用栈也占用 O(N) 空间一般二叉树场景下递归深度与path长度等于树高空间为 O(log N)O(N)。变体与延伸掌握本题的回溯写法后可自然迁移到同族题目路径总和 I只需判断是否存在合法路径找到即返回无需维护path与结果集路径总和 III路径不必从根出发、也不必止于叶需要额外引入前缀和或双重递归二叉树的所有路径257不再要求路径和仅枚举全部根到叶路径是本题去掉求和约束后的退化版本。这些题共享「先序遍历维护路径、叶子处结算、回溯弹出节点」的核心模式区别只在于结算条件与路径起止约束。小结核心框架 先序遍历递归 路径记录回溯5 步递推流程缺一不可记录答案时必须拷贝路径Python 用list(path)、Java 用new LinkedList(path)、C 用push_back的值语义复杂度稳定为 O(N) 时间、O(N) 空间适合面试中手写并解释「为什么不能直接 append(path)」完整可运行代码与测试用例见 Python、Java、C 三份文件可直接本地运行对照验证。【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考