树与图简单1 种解法
#257二叉树的所有路径
以“->”连接节点值，返回所有根到叶子的路径。
#二叉树#深度优先搜索#字符串
原题
给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [1,2,3,null,5] 输出：["1->2->5","1->3"]
示例 2：
输入：root = [1] 输出：["1"]
提示：
- 树中节点的数目在范围
[1, 100]内 -100 <= Node.val <= 100
解题主线
- 字符串不可变，向下递归创建新路径时无需显式回溯。
解法 1：DFS 构造字符串
沿递归路径累积前缀，到叶子时加入完整字符串。
-
时间复杂度： O(nh) 最坏，包含字符串复制成本
-
空间复杂度： O(h²) 最坏，递归链上的字符串总长度；不计结果
import java.util.*;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
class Solution {
public List<String> binaryTreePaths(TreeNode root) {
List<String> result = new ArrayList<>();
if (root != null) dfs(root, "", result);
return result;
}
private void dfs(TreeNode node, String prefix, List<String> result) {
// String 不可变，每个递归分支获得独立路径，无需显式撤销
String path = prefix.isEmpty() ? Integer.toString(node.val)
: prefix + "->" + node.val;
// 只有叶子才代表一条完整的根到叶路径
if (node.left == null && node.right == null) {
result.add(path);
return;
}
// 非空子树继续共享当前已构造好的路径前缀
if (node.left != null) dfs(node.left, path, result);
if (node.right != null) dfs(node.right, path, result);
}
}边界与易错点
- 只有叶子节点才把路径加入结果。
- 空树应返回空列表。
整理来源
由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。
leetcode/src/main/java/tree/Q257_binaryTreePaths.java