企业官网建设流程全解析

• 教程
• 文档
• 知识库

本篇基于 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 res

3.1 逐行解读

1. res = []：答案数组，用于收集所有完整路径；
2. 内部函数dfs(root, path)：path表示从根到当前节点为止已经拼好的路径字符串（不含分隔符尾缀）；
3. 空节点直接返回，这是递归的终止条件之一；
4. path += str(root.val)：把当前节点值拼接到路径末尾，此时path形如"1->2->5"的完整段落；
5. 叶子节点判定：not root.left and not root.right成立时，说明当前节点是叶子，将path加入res后返回；
6. 非叶子节点时按孩子的存在情况分三种分支调用：
   • 只有左子树（not root.right）：dfs(root.left, path + "->")；
   • 只有右子树（not root.left）：dfs(root.right, path + "->")；
   • 左右都有：分别递归左右子树。
7. 最后以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 res

BFS 版本空间占用通常高于递归版，但无需担心深树递归栈溢出，可作为补充思路。

六、同类题目串讲：把「路径」问题一网打尽

「根到叶路径」是二叉树面试题的经典母题，围绕它衍生出一系列变体，本仓库均已收录对应题解：

对比可见：

• 0257 的核心动作是字符串拼接：path + "->"；
• 0112 的核心动作是数值累加判断：currSum += root.val，叶子处比较是否等于targetSum；
• 0113 在 0112 基础上叠加回溯：维护可变path，命中条件时res.append(path[:])后再回退；
• 0129 把拼接语义换成十进制进位：total = pre_total * 10 + root.val。

四题共享同一套 DFS 递归骨架，差异只在于「沿路径传递什么、叶子处做什么判断」。掌握 0257 的模板后，其余题目只需替换路径的承载形式即可。

七、小结

1. 核心算法：深度优先搜索（DFS）+ 递归，先序式拼接路径；
2. 叶子判定：not root.left and not root.right，是输出路径的触发点；
3. 路径传递：字符串path + "->"向下传递（不可变）或列表 +pop()回退（可变）两种范式；
4. 复杂度：时间复杂度 $O(n^2)$（考虑路径字符串复制），空间复杂度 $O(n^2)$（递归栈 + 结果存储）；
5. 迁移能力：同一 DFS 模板可扩展到路径总和（0112）、路径总和 II（0113）、求根到叶数字之和（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。

• 教程
• 文档
• 知识库