LeetCode 257. 二叉树的所有路径

约 5 分钟
文章信息 14 个分类 5 个标签
分类
LeetCode CodeTop 简单 未解决 历史考题 10-20 腾讯 字节 阿里 美团 拼多多 百度 虾皮 猿辅导
标签
字符串 深度优先搜索 树 二叉树 回溯

题目描述

✅ 257. 二叉树的所有路径

image-20260928215952032

image-20260928215952033

题意分析

返回二叉树从根节点到每个叶子节点的全部路径，每条路径按经过顺序写出节点值，用 -> 连接，结果顺序不限。

叶子必须左右孩子都为空。只有一个孩子的节点仍是路径中途，不能提前结束；不同叶子对应不同路径，即使部分祖先相同，也需要分别保存完整结果。

解法：DFS 回溯构造路径

核心思路

[!blue]

DFS 从根向下走时，当前递归分支恰好就是一条路径的前缀。用共享的可变缓冲区 path 保存这个前缀，进入节点时追加当前值，到达叶子时便得到一条完整的根到叶路径。

共享缓冲区避免每到一个中间节点都复制整段字符串，但也意味着左右分支会操作同一份内容。因此进入节点之前先记下旧长度 length；本节点及其后代处理完后，把缓冲区截回该长度，让调用方看到的仍是进入之前的祖先路径。

这个恢复规则使兄弟分支互不干扰。左子树返回时，它添加的所有内容已经撤销，右子树接着使用的仍是相同祖先前缀；每一层都这样恢复，就可以完整枚举所有根到叶路径，而不会混入另一条分支的节点。

叶子处需要把当前缓冲区转换成独立字符串快照后加入答案。缓冲区稍后还要回滚并复用，已经保存的结果不能随之改变。记录旧长度也比固定删除几个字符更可靠：节点值可能为负数或多位数，按长度恢复能一次撤销本层追加的全部内容。

分隔符只在已有祖先前缀时追加，然后再追加当前值。这样根前面没有箭头，节点之间有且仅有一个箭头，叶子后面也不会多出分隔符。

解题步骤

  1. 创建答案列表和空路径缓冲区，从根节点启动 DFS。
  2. 遇到空节点直接返回；遇到真实节点，先保存缓冲区的旧长度。
  3. 如果路径已经非空，先追加 ->，再追加当前节点值。
  4. 若当前节点是叶子，将路径转换为字符串快照并保存；否则依次递归左右孩子。
  5. 无论当前是否为叶子，返回前都把缓冲区恢复到旧长度，继续交给上层使用。

代码实现

class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<>();

        dfs(root, new StringBuilder(), res);

        return res;
    }

    private void dfs(TreeNode node, StringBuilder path, List<String> res) {
        if (node == null) {
            return;
        }

        // 保存进入当前节点之前的长度，负数和多位数都按长度完整撤销。
        int length = path.length();

        if (length > 0) {
            path.append("->");
        }

        path.append(node.val);

        if (node.left == null && node.right == null) {
            res.add(path.toString());
        } else {
            dfs(node.left, path, res);
            dfs(node.right, path, res);
        }

        // 无论是否命中叶子，都恢复祖先路径后再返回。
        path.setLength(length);
    }
}

import "strconv"

func binaryTreePaths(root *TreeNode) []string {
    res := make([]string, 0)
    path := make([]byte, 0)
    var dfs func(*TreeNode)
    dfs = func(node *TreeNode) {
        if node == nil {
            return
        }

        // 保存进入当前节点之前的长度，负数和多位数都按长度完整撤销。
        length := len(path)
        if length > 0 {
            path = append(path, '-', '>')
        }
        path = strconv.AppendInt(path, int64(node.Val), 10)

        if node.Left == nil && node.Right == nil {
            res = append(res, string(path))
        } else {
            dfs(node.Left)
            dfs(node.Right)
        }
        // 无论是否命中叶子，都恢复祖先路径后再返回。
        path = path[:length]
    }
    dfs(root)
    return res
}

复杂度分析

设节点数为 n，树高为 h，全部输出字符串的字符总数为 S，节点数值的字符长度在题目范围内有常数上界。

  • 时间复杂度：$O(n+S)$。每个节点只进入一次，叶子处复制完整路径的总成本等于输出规模；最坏可写为 $O(nh)$。
  • 空间复杂度：不计答案为 $O(h)$，递归栈和当前路径都只保存一条根到节点的分支；计入返回字符串则还需要 $O(S)$。

关键点总结

[!green]

  • 进入节点时路径代表祖先前缀，追加后代表当前路径，离开时必须恢复原前缀。
  • 共享缓冲区负责当前分支，字符串快照负责长期保存答案，两者职责不同。
  • 只在叶子处记录结果，保证每条输出路径都从根完整延伸到叶子。

易错点总结

[!yellow]

  • 忘记回滚路径，兄弟分支会继续接在前一个分支后面，形成树中不存在的路径。
  • 在追加内容之后才保存旧长度，就无法在返回时删除本层新增的内容。
  • 按固定字符数回退，遇到负数或多位数会多删或少删；应恢复到进入前记录的长度。
  • 用“任一孩子为空”判断叶子，会漏掉仍可延伸到另一侧孩子的完整路径。
  • 保存路径后立即返回而不恢复缓冲区，会让叶子内容残留；代码统一在函数末尾回滚。
  • 无条件在节点前后添加箭头，会让输出首尾多出分隔符；只在已有前缀时添加即可。

相似题目

题目 难度 关联与区别
113. 路径总和 II 中等 路径枚举相同，原题只保存和为目标的根到叶路径，本题不加和的筛选。
112. 路径总和 简单 原题仅判断是否存在满足路径和的根到叶路径，本题需要保存所有路径文本。
129. 求根节点到叶节点数字之和 中等 回溯维护从根到当前节点的路径；本题输出所有根到叶的字符串路径，该题逐层按十进制累加根到叶数字。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/53054646
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！