企业官网建设流程全解析

剑指 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为空，则直接返回；
• 递推工作（五个固定步骤）：
  1. 路径更新：将当前节点值root.val加入路径path；
  2. 目标值更新：tar = tar - root.val（即目标值tar从sum一路减下去，最终期望减至 0）；
  3. 路径记录：当 ①root为叶节点且②tar == 0时，将此路径path加入res；
  4. 先序遍历：递归左子节点、右子节点；
  5. 路径恢复：向上回溯前，将当前节点从路径path中删除，即执行path.pop()。

其中第 3 步的“叶节点”判断必不可少：题目要求路径必须在叶节点终止。若只判断tar == 0而节点还有子树，会错误地把非完整路径计入结果。

三、仓库源码逐行解析（Python / Java / C++）

仓库在sword_for_offer/codes目录下为本题提供了三种语言的完整可运行实现，每份代码都自带测试用例与驱动代码。下面以 Python 版为主干对照讲解，再指出各语言实现差异点。

3.1 Python 实现

参见 Python 解题代码，核心解法位于Solution.pathSum内部嵌套的recur函数（#L15-L24）：

class 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-L32：

class Solution { LinkedList<List<Integer>> res = new LinkedList<>(); LinkedList<Integer> path = new LinkedList<>(); public List<List<Integer>> 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-L30：

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(); }

C++ 成员vector<int> 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对象也会随之改变，因此无法实现结果记录。

正确做法在三语言中的写法对照如下（均可在仓库源码中逐行对应）：

三者的原理一致：拷贝一个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_ii（C++） 与 lc_113_path_sum_ii.py（Python） 中提供了同框架实现，可对照练习；
• 剑指 Offer 37 序列化二叉树：先序遍历序列化的写法见 sfo_37（Python） 对应的sfo_37系列目录，同样依赖“访问根节点时先做处理”的先序顺序。

掌握本文五步回溯模板（append → tar 减 → 判叶记录 → 左右递归 → pop）后，以上题目均可直接套用，只需替换“记录条件”与“目标值更新方式”两处逻辑。

参考资料（仓库内文件）

• 题解文档：剑指 Offer 34. 二叉树中和为某一值的路径
• Python 实现：sfo_34_all_xsum_paths_in_a_binary_tree_s1.py
• Java 实现：sfo_34_all_xsum_paths_in_a_binary_tree_s1.java
• C++ 实现：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