关注文末推广名片，即可免费获得本题测试源码！

题目来源：LeetCode257：二叉树的所有路径

问题抽象： 给定一个二叉树的根节点 root，要求生成所有 从根节点到叶子节点的路径 的字符串表示，需满足以下核心需求：

1. 路径定义：

   • 起点：必须从根节点 root 开始；
   • 终点：必须到达 叶子节点（无左/右子节点的节点）；
   • 路径序列：包含路径上所有节点的值（按父→子顺序排列）。

2. 输出格式：

   • 每条路径为字符串，节点值间用 “->” 连接（如 "1->2->5"）；
   • 若树仅一个节点（根节点即叶子），输出仅含该节点值（如 ["1"]）；
   • 结果列表顺序 任意（通常前序遍历顺序）。

3. 输入约束：

   • 节点数 ∈ [0, 100]（空树返回空列表）；
   • 节点值 ∈ [-100, 100]（含负整数）。

4. 边界处理：

   • 空树：返回空列表 []；
   • 单节点树：返回 [str(root.val)]；
   • 非叶子节点：路径必须延伸至叶子节点（如根有左子时，路径不能止于根）。

5. 遍历要求：

   • 时间复杂度 O(n²)（每条路径需拼接字符串，路径平均长度 O(h)，总操作数 O(n*h)）；
   • 空间复杂度 O(n)（递归栈深度最坏 O(n)，结果存储 O(n)）。

输入：二叉树根节点 root（如 [1,2,3,null,5]）
输出：字符串列表（如 ["1->2->5","1->3"]）。

---

解题思路

使用深度优先搜索（DFS）遍历二叉树，记录根节点到当前节点的路径。当遇到叶子节点时，将当前路径转换为字符串加入结果集。为优化性能：

1. 使用 StringBuilder 构建路径：避免字符串拼接产生大量临时对象。
2. 回溯时重置 StringBuilder：记录操作前的长度，递归后重置至该长度，避免重复创建对象。
3. 延迟添加箭头：只有非根节点时才添加 ->，减少条件判断。

步骤：

1. 若当前节点为空，直接返回。
2. 记录当前 StringBuilder 长度（用于回溯）。
3. 若非根节点（路径非空），先添加 -> 再添加节点值。
4. 若当前节点是叶子节点，将路径加入结果集。
5. 递归处理左右子树。
6. 回溯：重置 StringBuilder 至之前记录的长度。

---

代码实现（Java版）🔥点击下载源码

class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> result = new ArrayList<>();
        dfs(root, new StringBuilder(), result);
        return result;
    }

    private void dfs(TreeNode node, StringBuilder path, List<String> result) {
        if (node == null) return;
        
        // 记录当前StringBuilder长度以便回溯
        int len = path.length();
        
        // 若非根节点，先添加箭头
        if (len > 0) {
            path.append("->");
        }
        // 添加当前节点值
        path.append(node.val);
        
        // 叶子节点：将路径加入结果
        if (node.left == null && node.right == null) {
            result.add(path.toString());
        } 
        // 非叶子节点：递归处理子树
        else {
            dfs(node.left, path, result);
            dfs(node.right, path, result);
        }
        
        // 回溯：重置StringBuilder长度
        path.setLength(len);
    }
}

---

代码说明

1. 初始化：binaryTreePaths 方法初始化结果列表并启动 DFS。
2. DFS 递归：
   • 记录长度：len = path.length() 保存当前状态。
   • 构建路径：非根节点时添加 ->，再添加节点值。
   • 处理叶子节点：直接保存路径字符串。
   • 递归子树：继续遍历左右子树。
   • 回溯：path.setLength(len) 重置路径状态。
3. 性能优化：
   • 时间：每个节点仅访问一次，时间复杂度 $O(N)$。
   • 空间：递归栈深度 $O(H)$（$H$ 为树高），StringBuilder 复用减少内存分配。

---

提交详情（执行用时、内存消耗）