剑指 Offer 34二叉树中和为某一值的路径——回溯法先序遍历 路径记录的完整实现【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book本篇技术指南围绕 LeetCode-Book 仓库中《剑指 Offer 34. 二叉树中和为某一值的路径》题解展开讲清如何用“先序遍历 路径记录”的回溯框架找出二叉树中所有和为目标值的根到叶路径。读完你不仅能掌握recur递归函数的五个标准步骤入栈、减目标、判叶、递归、回溯还能对照仓库中 Python / Java / C 三份可运行源码理解为什么保存路径时必须“拷贝”而非“引用”。一、问题分析为什么必须用回溯本题是典型的二叉树方案搜索问题。题目给定一棵二叉树的根节点root和一个整数sum目标值要求返回所有路径和为目标值的路径且路径必须从根节点出发、在叶节点处结束这是剑指 Offer 34 与 LeetCode 路径总和问题的关键约束。解题框架由两部分组成先序遍历按照“根、左、右”的顺序遍历树的所有节点保证从根到叶的每条路径都被访问到路径记录在先序遍历中记录从根节点到当前节点的路径。当路径满足 ① 根节点到叶节点形成的路径且② 各节点值的和等于目标值sum时将此路径加入结果列表。之所以用回溯而不是简单 DFS 计数是因为题目要求返回路径本身必须维护一个随递归深入而增长、随递归返回而缩回的“当前路径”容器这正是回溯法的核心特征。二、算法流程两个函数的职责划分题解将整体逻辑拆分为一个入口函数和一个递归函数pathSum(root, sum)函数入口初始化结果列表res、路径列表path返回值执行完递归后返回res。recur(root, tar)函数递归主体递推参数当前节点root、当前目标值tar注意这里把“剩余还需凑出的和”作为参数逐层下传而不是累加路径和再比较代码更简洁终止条件若节点root为空则直接返回递推工作五个固定步骤路径更新将当前节点值root.val加入路径path目标值更新tar tar - root.val即目标值tar从sum一路减下去最终期望减至 0路径记录当 ①root为叶节点且②tar 0时将此路径path加入res先序遍历递归左子节点、右子节点路径恢复向上回溯前将当前节点从路径path中删除即执行path.pop()。其中第 3 步的“叶节点”判断必不可少题目要求路径必须在叶节点终止。若只判断tar 0而节点还有子树会错误地把非完整路径计入结果。三、仓库源码逐行解析Python / Java / C仓库在sword_for_offer/codes目录下为本题提供了三种语言的完整可运行实现每份代码都自带测试用例与驱动代码。下面以 Python 版为主干对照讲解再指出各语言实现差异点。3.1 Python 实现参见 Python 解题代码核心解法位于Solution.pathSum内部嵌套的recur函数#L15-L24class Solution: def pathSum(self, root: TreeNode, sum: 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, sum) return res几个值得注意的实现细节res与path在pathSum作用域内定义recur作为闭包直接读写它们无需类成员变量天然支持同一Solution实例被多次调用判断叶节点的写法是not root.left and not root.right与题解中“① 且 ②”两个条件一一对应path.pop()写在两个递归调用之后确保左右子树都处理完后才撤销当前节点——这是回溯顺序最容易写错的地方。3.2 Java 实现参见 Java 解题代码。Java 版将res与path提升为类成员变量#L14-L15递归函数recur位于 #L22-L32class Solution { LinkedListListInteger res new LinkedList(); LinkedListInteger path new LinkedList(); public ListListInteger pathSum(TreeNode root, int sum) { recur(root, sum); 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 LinkedList(path)); recur(root.left, tar); recur(root.right, tar); path.removeLast(); } }回溯动作对应的是path.removeLast()从链表尾部弹出最后一个元素。由于path用的是LinkedList尾部增删都是 O(1)比ArrayList更贴合回溯场景。3.3 C 实现参见 C 解题代码recur私有成员函数位于 #L20-L30void 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(); }C 成员vectorint path用push_back/pop_back完成路径的伸缩res.push_back(path)由于vector的拷贝构造天然就是一次“值拷贝”语义上等价于 Java 的new LinkedList(path)和 Python 的list(path)。3.4 测试用例与可验证结果三份代码内置了同一个测试用例LeetCode 官方示例层序序列[5, 4, 8, 11, null, 13, 4, 7, 2, null, null, 5, 1, ...]构建树、目标值sum 22见 Python 版测试段 与 C 版测试段。手工验算该测试用例路径5 → 4 → 11 → 2和为 22且 2 是叶节点成立路径5 → 8 → 4 → 5和为 22且 5 是叶节点成立路径5 → 8 → 4 → 1和为 18不成立。因此三份代码运行后的预期输出均为[[5, 4, 11, 2], [5, 8, 4, 5]]可直接编译/运行仓库代码验证。三个版本都通过include公共目录复用TreeNode与层序建树工具如 C 头文件汇总、Python 二叉树工具保证测试代码与线上判题输入构造方式一致。四、关键陷阱保存路径必须“拷贝”不能“引用”这是题解中专门强调、也是三种语言表现不一致最容易踩坑的一点记录路径时若直接执行res.append(path)则是将此path对象加入了res后续path改变时res中的path对象也会随之改变因此无法实现结果记录。正确做法在三语言中的写法对照如下均可在仓库源码中逐行对应语言正确写法仓库代码位置原理Pythonres.append(list(path))Python #L21用list()构造一个浅拷贝再入列Javares.add(new LinkedList(path))Java #L28用带参构造器复制一份新链表Cres.push_back(path)C #L26vector::push_back默认拷贝值语义三者的原理一致拷贝一个path的当前快照存入res而不是把会持续变动的path容器本身塞进去。如果 Python 写成res.append(path)所有已记录路径最终都会等于回溯结束时的空列表Java 写成res.add(path)则所有路径会随removeLast一起被清空。C 由于值语义默认安全反而是三种语言中最不容易出错的。五、复杂度分析继承题解给出的结论时间复杂度 O(N)N为二叉树节点数先序遍历需要访问所有节点每个节点只做常数时间的入栈、判叶、出栈操作空间复杂度 O(N)除结果存储外递归调用栈与path的最深规模等于树高最差情况下树退化为链表path存储所有N个节点使用 O(N) 额外空间。六、延伸同一框架可复用的相邻问题从源码结构看本题的“先序遍历 路径记录 回溯”骨架是本仓库中多条二叉树路径类题目的通用模板可按同一模式迁移LeetCode 113 路径总和 II与本题同型仓库在 lc_113_path_sum_iiC 与 lc_113_path_sum_ii.pyPython 中提供了同框架实现可对照练习剑指 Offer 37 序列化二叉树先序遍历序列化的写法见 sfo_37Python 对应的sfo_37系列目录同样依赖“访问根节点时先做处理”的先序顺序。掌握本文五步回溯模板append → tar 减 → 判叶记录 → 左右递归 → pop后以上题目均可直接套用只需替换“记录条件”与“目标值更新方式”两处逻辑。参考资料仓库内文件题解文档剑指 Offer 34. 二叉树中和为某一值的路径Python 实现sfo_34_all_xsum_paths_in_a_binary_tree_s1.pyJava 实现sfo_34_all_xsum_paths_in_a_binary_tree_s1.javaC 实现sfo_34_all_xsum_paths_in_a_binary_tree_s1.cpp【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 剑指 Offer 34：二叉树中和为某一值的路径——回溯法（先序遍历 + 路径记录）的完整实现
剑指 Offer 34二叉树中和为某一值的路径——回溯法先序遍历 路径记录的完整实现【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book本篇技术指南围绕 LeetCode-Book 仓库中《剑指 Offer 34. 二叉树中和为某一值的路径》题解展开讲清如何用“先序遍历 路径记录”的回溯框架找出二叉树中所有和为目标值的根到叶路径。读完你不仅能掌握recur递归函数的五个标准步骤入栈、减目标、判叶、递归、回溯还能对照仓库中 Python / Java / C 三份可运行源码理解为什么保存路径时必须“拷贝”而非“引用”。一、问题分析为什么必须用回溯本题是典型的二叉树方案搜索问题。题目给定一棵二叉树的根节点root和一个整数sum目标值要求返回所有路径和为目标值的路径且路径必须从根节点出发、在叶节点处结束这是剑指 Offer 34 与 LeetCode 路径总和问题的关键约束。解题框架由两部分组成先序遍历按照“根、左、右”的顺序遍历树的所有节点保证从根到叶的每条路径都被访问到路径记录在先序遍历中记录从根节点到当前节点的路径。当路径满足 ① 根节点到叶节点形成的路径且② 各节点值的和等于目标值sum时将此路径加入结果列表。之所以用回溯而不是简单 DFS 计数是因为题目要求返回路径本身必须维护一个随递归深入而增长、随递归返回而缩回的“当前路径”容器这正是回溯法的核心特征。二、算法流程两个函数的职责划分题解将整体逻辑拆分为一个入口函数和一个递归函数pathSum(root, sum)函数入口初始化结果列表res、路径列表path返回值执行完递归后返回res。recur(root, tar)函数递归主体递推参数当前节点root、当前目标值tar注意这里把“剩余还需凑出的和”作为参数逐层下传而不是累加路径和再比较代码更简洁终止条件若节点root为空则直接返回递推工作五个固定步骤路径更新将当前节点值root.val加入路径path目标值更新tar tar - root.val即目标值tar从sum一路减下去最终期望减至 0路径记录当 ①root为叶节点且②tar 0时将此路径path加入res先序遍历递归左子节点、右子节点路径恢复向上回溯前将当前节点从路径path中删除即执行path.pop()。其中第 3 步的“叶节点”判断必不可少题目要求路径必须在叶节点终止。若只判断tar 0而节点还有子树会错误地把非完整路径计入结果。三、仓库源码逐行解析Python / Java / C仓库在sword_for_offer/codes目录下为本题提供了三种语言的完整可运行实现每份代码都自带测试用例与驱动代码。下面以 Python 版为主干对照讲解再指出各语言实现差异点。3.1 Python 实现参见 Python 解题代码核心解法位于Solution.pathSum内部嵌套的recur函数#L15-L24class Solution: def pathSum(self, root: TreeNode, sum: 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, sum) return res几个值得注意的实现细节res与path在pathSum作用域内定义recur作为闭包直接读写它们无需类成员变量天然支持同一Solution实例被多次调用判断叶节点的写法是not root.left and not root.right与题解中“① 且 ②”两个条件一一对应path.pop()写在两个递归调用之后确保左右子树都处理完后才撤销当前节点——这是回溯顺序最容易写错的地方。3.2 Java 实现参见 Java 解题代码。Java 版将res与path提升为类成员变量#L14-L15递归函数recur位于 #L22-L32class Solution { LinkedListListInteger res new LinkedList(); LinkedListInteger path new LinkedList(); public ListListInteger pathSum(TreeNode root, int sum) { recur(root, sum); 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 LinkedList(path)); recur(root.left, tar); recur(root.right, tar); path.removeLast(); } }回溯动作对应的是path.removeLast()从链表尾部弹出最后一个元素。由于path用的是LinkedList尾部增删都是 O(1)比ArrayList更贴合回溯场景。3.3 C 实现参见 C 解题代码recur私有成员函数位于 #L20-L30void 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(); }C 成员vectorint path用push_back/pop_back完成路径的伸缩res.push_back(path)由于vector的拷贝构造天然就是一次“值拷贝”语义上等价于 Java 的new LinkedList(path)和 Python 的list(path)。3.4 测试用例与可验证结果三份代码内置了同一个测试用例LeetCode 官方示例层序序列[5, 4, 8, 11, null, 13, 4, 7, 2, null, null, 5, 1, ...]构建树、目标值sum 22见 Python 版测试段 与 C 版测试段。手工验算该测试用例路径5 → 4 → 11 → 2和为 22且 2 是叶节点成立路径5 → 8 → 4 → 5和为 22且 5 是叶节点成立路径5 → 8 → 4 → 1和为 18不成立。因此三份代码运行后的预期输出均为[[5, 4, 11, 2], [5, 8, 4, 5]]可直接编译/运行仓库代码验证。三个版本都通过include公共目录复用TreeNode与层序建树工具如 C 头文件汇总、Python 二叉树工具保证测试代码与线上判题输入构造方式一致。四、关键陷阱保存路径必须“拷贝”不能“引用”这是题解中专门强调、也是三种语言表现不一致最容易踩坑的一点记录路径时若直接执行res.append(path)则是将此path对象加入了res后续path改变时res中的path对象也会随之改变因此无法实现结果记录。正确做法在三语言中的写法对照如下均可在仓库源码中逐行对应语言正确写法仓库代码位置原理Pythonres.append(list(path))Python #L21用list()构造一个浅拷贝再入列Javares.add(new LinkedList(path))Java #L28用带参构造器复制一份新链表Cres.push_back(path)C #L26vector::push_back默认拷贝值语义三者的原理一致拷贝一个path的当前快照存入res而不是把会持续变动的path容器本身塞进去。如果 Python 写成res.append(path)所有已记录路径最终都会等于回溯结束时的空列表Java 写成res.add(path)则所有路径会随removeLast一起被清空。C 由于值语义默认安全反而是三种语言中最不容易出错的。五、复杂度分析继承题解给出的结论时间复杂度 O(N)N为二叉树节点数先序遍历需要访问所有节点每个节点只做常数时间的入栈、判叶、出栈操作空间复杂度 O(N)除结果存储外递归调用栈与path的最深规模等于树高最差情况下树退化为链表path存储所有N个节点使用 O(N) 额外空间。六、延伸同一框架可复用的相邻问题从源码结构看本题的“先序遍历 路径记录 回溯”骨架是本仓库中多条二叉树路径类题目的通用模板可按同一模式迁移LeetCode 113 路径总和 II与本题同型仓库在 lc_113_path_sum_iiC 与 lc_113_path_sum_ii.pyPython 中提供了同框架实现可对照练习剑指 Offer 37 序列化二叉树先序遍历序列化的写法见 sfo_37Python 对应的sfo_37系列目录同样依赖“访问根节点时先做处理”的先序顺序。掌握本文五步回溯模板append → tar 减 → 判叶记录 → 左右递归 → pop后以上题目均可直接套用只需替换“记录条件”与“目标值更新方式”两处逻辑。参考资料仓库内文件题解文档剑指 Offer 34. 二叉树中和为某一值的路径Python 实现sfo_34_all_xsum_paths_in_a_binary_tree_s1.pyJava 实现sfo_34_all_xsum_paths_in_a_binary_tree_s1.javaC 实现sfo_34_all_xsum_paths_in_a_binary_tree_s1.cpp【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考