教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本篇基于 AlgoNote 算法通关手册的题解文档 docs/solutions/0200-0299/binary-tree-paths.md 展开围绕 LeetCode 0257「二叉树的所有路径」讲解以深度优先搜索DFS为核心的解题思路、递归代码实现与复杂度分析并延伸回溯、广度优先搜索等变体写法。读完本篇你将掌握「遍历二叉树 拼接根到叶路径」这一类问题的通用套路可直接迁移到路径总和、求根到叶数字之和等同类题目。一、题目概述题目名称二叉树的所有路径Binary Tree Paths题目链接[0257. 二叉树的所有路径 - 力扣]标签树、深度优先搜索、字符串、回溯、二叉树难度简单题目大意给定一个二叉树的根节点root要求返回所有从根节点到叶子节点的路径每条路径以字符串形式输出节点值之间用-分隔。示例输入root [1,2,3,null,5] 输出[1-2-5, 1-3]其中1-2-5表示从根节点 1 出发经左子节点 2最终到达叶子节点 5 的完整路径。这里的叶子节点指度为 0、没有左右子节点的节点参见 docs/05_tree/05_01_tree_basic.md 中关于叶子节点的定义。二、解题思路深度优先搜索DFS本题的核心数据结构是二叉树。要求输出「所有根到叶子路径」意味着我们需要从上到下、逐节点深入直到无法继续为止——这正是**深度优先搜索DFS**的典型应用场景。关于 DFS 的基本思想沿一条路径尽可能深入走到头再回退尝试其他分支可参见 docs/06_graph/06_03_graph_dfs.md 的算法步骤说明二叉树的递归遍历模板访问根、递归左子树、递归右子树则对应 docs/05_tree/05_02_binary_tree_traverse.md 中的前序遍历递归实现。在递归遍历二叉树时需同时考虑当前节点和左右孩子节点并始终维护一条「从根到当前节点」的已拼接路径如果当前节点不是叶子节点则将当前节点值加入已拼接路径中并继续递归遍历其左、右子树如果当前节点是叶子节点root.left与root.right均为空则将当前节点值加入已拼接路径中并将整条路径加入答案数组res返回上一层。这一过程本质上是一种先序遍历式的前向拼接每个节点只会被「拼」一次路径字符串随递归向下传递天然满足从根到叶的顺序。三、代码实现递归 字符串拼接原题解文档给出的实现如下class Solution: def binaryTreePaths(self, root: TreeNode) - List[str]: res [] def dfs(root, path): if not root: return path str(root.val) if not root.left and not root.right: res.append(path) elif not root.right: dfs(root.left, path -) elif not root.left: dfs(root.right, path -) else: dfs(root.left, path -) dfs(root.right, path -) dfs(root, ) return res3.1 逐行解读res []答案数组用于收集所有完整路径内部函数dfs(root, path)path表示从根到当前节点为止已经拼好的路径字符串不含分隔符尾缀空节点直接返回这是递归的终止条件之一path str(root.val)把当前节点值拼接到路径末尾此时path形如1-2-5的完整段落叶子节点判定not root.left and not root.right成立时说明当前节点是叶子将path加入res后返回非叶子节点时按孩子的存在情况分三种分支调用只有左子树not root.rightdfs(root.left, path -)只有右子树not root.leftdfs(root.right, path -)左右都有分别递归左右子树。最后以dfs(root, )从根节点、空路径开始启动遍历。3.2 为什么是「先判叶子、再分分支」原题解的顺序设计有两个精妙之处先拼接、后判定无论当前节点是叶子还是内部节点都要先把自己的值拼进路径保证路径信息不丢失分支枚举代替统一递归对左、右孩子的存在性分别处理避免在空子树上多做无意义的path -拼接也使叶子判断逻辑与内部节点推进逻辑彻底分离语义更清晰。如果希望代码更精简也可以将左右孩子的递归统一写成class Solution: def binaryTreePaths(self, root: TreeNode) - List[str]: res [] def dfs(node, path): if not node: return path str(node.val) if not node.left and not node.right: res.append(path) else: dfs(node.left, path -) dfs(node.right, path -) dfs(root, ) return res该写法与 docs/05_tree/05_02_binary_tree_traverse.md 中的递归前序遍历框架完全一致访问根 → 递归左 → 递归右更便于记忆和迁移。原题解的分支写法与统一写法在结果上等价读者可按喜好选择。四、复杂度分析时间复杂度$O(n^2)$其中 $n$ 为二叉树的节点总数。每个节点都会被访问一次$O(n)$同时每次到达叶子节点时需要拷贝一份路径字符串path或将其加入res路径长度最坏可达 $O(n)$因此整体为 $O(n^2)$。若按只统计节点访问次数的最朴素口径也可记为主体遍历的 $O(n)$但考虑字符串复制成本$O(n^2)$ 是更严谨的估计。空间复杂度$O(n^2)$。递归函数依赖系统调用栈栈深度取决于二叉树高度最坏情况下链状树递归深度为 $n$即 $O(n)$ 的栈空间同时res中需要保存 $O(n)$ 条路径每条路径长度最坏 $O(n)$合计 $O(n^2)$。需要说明本题为「简单」难度主流判题对常系数并不敏感两种复杂度口径都能被接受重点在于理解递归深度与路径复制两个维度的开销来源。五、延伸写法与变体5.1 回溯写法维护路径列表 回退原题解的path是不可变字符串每次递归传递新串天然避免了污染。若改用可变列表记录路径节点则需要在递归返回前做「回退」操作path.pop()这就是回溯思想。这一写法与 docs/solutions/0100-0199/path-sum-ii.md路径总和 II中的回溯模板完全同构class Solution: def binaryTreePaths(self, root: TreeNode) - List[str]: res [] path [] def dfs(node): if not node: return path.append(str(node.val)) if not node.left and not node.right: res.append(-.join(path)) else: dfs(node.left) dfs(node.right) path.pop() # 回退撤销对当前节点的选择 dfs(root) return res其中res.append(-.join(path))将节点列表[1, 2, 5]拼接为字符串1-2-5。可变列表 pop()回退是「树/图上的路径类问题」的标准回溯范式与 docs/06_graph/06_03_graph_dfs.md 中「访问后回退到上一个分叉点」的 DFS 回溯语义一脉相承。5.2 广度优先搜索BFS写法DFS 自上而下逐层深入BFS 则逐层扩展。若用队列同时维护「当前节点」与「当前路径」同样可以得到全部根叶路径from collections import deque class Solution: def binaryTreePaths(self, root: TreeNode) - List[str]: if not root: return [] res [] queue deque([(root, str(root.val))]) while queue: node, path queue.popleft() if not node.left and not node.right: res.append(path) if node.left: queue.append((node.left, path - str(node.left.val))) if node.right: queue.append((node.right, path - str(node.right.val))) return resBFS 版本空间占用通常高于递归版但无需担心深树递归栈溢出可作为补充思路。六、同类题目串讲把「路径」问题一网打尽「根到叶路径」是二叉树面试题的经典母题围绕它衍生出一系列变体本仓库均已收录对应题解题目题解位置与本题的关系0257. 二叉树的所有路径binary-tree-paths.md输出全部根叶路径字符串本文0112. 路径总和path-sum.md判断是否存在「路径和 targetSum」的根叶路径DFS 携带currSum累加0113. 路径总和 IIpath-sum-ii.md输出所有「路径和 targetSum」的路径节点序列回溯 减枝求和0129. 求根节点到叶节点数字之和sum-root-to-leaf-numbers.md将路径视为数字pre_total * 10 val求和而非拼接字符串对比可见0257 的核心动作是字符串拼接path -0112 的核心动作是数值累加判断currSum root.val叶子处比较是否等于targetSum0113 在 0112 基础上叠加回溯维护可变path命中条件时res.append(path[:])后再回退0129 把拼接语义换成十进制进位total pre_total * 10 root.val。四题共享同一套 DFS 递归骨架差异只在于「沿路径传递什么、叶子处做什么判断」。掌握 0257 的模板后其余题目只需替换路径的承载形式即可。七、小结核心算法深度优先搜索DFS 递归先序式拼接路径叶子判定not root.left and not root.right是输出路径的触发点路径传递字符串path -向下传递不可变或列表 pop()回退可变两种范式复杂度时间复杂度 $O(n^2)$考虑路径字符串复制空间复杂度 $O(n^2)$递归栈 结果存储迁移能力同一 DFS 模板可扩展到路径总和0112、路径总和 II0113、求根到叶数字之和0129等系列题目。本篇题解内容对应仓库中的 docs/solutions/0200-0299/binary-tree-paths.md完整题目索引可查阅 docs/00_preface/00_05_solutions_list.md相关二叉树遍历与 DFS 基础可回看 docs/05_tree/05_02_binary_tree_traverse.md 与 docs/06_graph/06_03_graph_dfs.md。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐KubeEdge 项目中的 gziphandlerGo HTTP 响应透明 Gzip 压缩中间件完全指南KubeEdge 项目中的 gziphandlerGo HTTP 响应透明 Gzip 压缩中间件完全指南 导读 本文围绕 KubeEdge 仓库中第三方依赖教程文档知识库LeetCode 0094 二叉树的中序遍历递归与显式栈迭代双解法详解AlgoNote 算法通关手册LeetCode 0094 二叉树的中序遍历递归与显式栈迭代双解法详解AlgoNote 算法通关手册 本篇技术指南围绕「算法通关手册」AlgoNote 仓教程文档知识库Gas Town Polecat 角色协议深度解析从 CLAUDE.md 模板看自主 Worker 的完整生命周期纪律Gas Town Polecat 角色协议深度解析从 CLAUDE.md 模板看自主 Worker 的完整生命周期纪律 导读 本文以 Gas Townmu教程文档知识库上一篇深度剖析EASY-HWID-SPOOFERWindows内核级硬件信息伪装技术终极指南下一篇如何3分钟让通达信自动画缠论中枢告别手动画线的终极解决方案创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考