LeetCode 257. 二叉树的所有路径

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

题目描述

✅ 257. 二叉树的所有路径

image-20250418205204011

题意分析

输入一棵二叉树的根节点，输出所有「从根节点到叶子节点」的路径，每条路径写成 1->2->5 这样的字符串，返回顺序不限。

题面有几个必须抠准的字眼。「叶子节点」指左右孩子都为空的节点，只有一个孩子的节点不算叶子，所以路径不能在半路截断；「从根开始」意味着每条路径都以根节点值打头，不存在从中间起步的路径；分隔符 -> 只出现在相邻两个节点值之间，路径首尾都不带。节点数范围是 $[1, 100]$，即树非空，但节点值可能是负数，字符串里出现 -3 这样的片段是正常的，不能用字符长度去猜节点个数。

边界情况：只有一个节点时，这个节点既是根又是叶，答案是单元素列表 ["1"]，此时一个 -> 都不该出现；某个节点只有右孩子时，不能因为左孩子为空就把它当叶子记录，必须继续往右走。答案条数等于叶子数量，每条路径长度是该叶子的深度，因此输出规模本身可以达到 $O(n \cdot h)$ 字符。

解法：DFS 回溯构造路径

核心思路

根到叶路径天然适合深度优先搜索：递归进入节点时把节点值加入当前路径，只有到达叶子时才把完整路径加入答案，随后回退到父节点继续搜索另一棵子树。

Java 用 StringBuilder、Go 用 []byte 维护共享缓冲区，避免每层复制整条路径。递归契约是：进入 dfs(node) 时，缓冲区保存根到 node 父节点的路径；离开时必须恢复到完全相同的状态。进入后先记录旧长度，再追加本节点，函数结束前截回旧长度。

正确性可按递归契约说明：DFS 会访问每个节点；只有左右孩子都为空时才记录，因此不会产生半截路径；到达叶子时缓冲区恰好包含从根到该叶子的所有节点。叶子处复制快照，回滚则保证兄弟分支互不污染。

解题步骤

  • 初始化答案列表和空路径缓冲区，从根节点开始 DFS。
  • 进入节点时记录缓冲区旧长度；路径非空则先追加 ->，再追加当前值。
  • 若当前节点是叶子，将 path.toString() 作为快照加入答案。
  • 否则继续递归左右孩子，保证所有根到叶路径都会被枚举。
  • 返回父节点前把缓冲区恢复到旧长度，清除本分支留下的内容。

对 [1,2,3,null,5]，DFS 先得到 1->2->5；回退到根路径 1 后再进入右子树，得到 1->3。若不回滚，第二条路径会错误地带上左分支内容。

代码实现

import java.util.*;

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
}

复杂度分析

  • 时间复杂度：$O(n + S)$，其中 $n$ 是节点数，$S$ 是所有输出路径的字符总数；最坏可写成 $O(n \cdot h)$。遍历每个节点一次，叶子处复制当前路径。
  • 空间复杂度：$O(h)$，不计答案；递归栈和共享路径缓冲区的长度都与树高 $h$ 成正比。

关键点总结

  • 递归契约要同时包含两件事：进入时路径代表父节点，离开时恢复原状。
  • 只有左右孩子都为空才是叶子，只有一个孩子的节点不能提前记录。
  • 共享可变缓冲区时，需要在叶子处生成快照、在返回前回滚。
  • 分隔符只在已有祖先路径时追加，避免路径开头或结尾出现多余的 ->。

易错点总结

  • 忘记回滚缓冲区会污染兄弟分支，例如第二条路径可能变成 1->2->5->3。
  • 在追加之后才记录旧长度，回滚时无法删除当前节点；存档必须发生在本层修改之前。
  • 用 left == null || right == null 判断叶子，会把只有一个孩子的节点误判为叶子；必须两边都为空。
  • 叶子处分支若提前 return，必须先回滚；当前实现统一在函数末尾回滚，避免遗漏。
  • 无条件追加 -> 会让单节点树输出 ->1，应只在路径非空时追加分隔符。

相似题目

题目 难度 考察点
112. 路径总和 简单 只判存在、可提前返回
113. 路径总和 II 中等 列表快照拷贝
129. 求根节点到叶节点数字之和 中等 路径数字按位累加
404. 左叶子之和 简单 由父节点识别左叶子
1022. 从根到叶的二进制数之和 简单 位运算维护路径值
LCR 049. 求根节点到叶节点数字之和 中等 同型题、数值版路径
剑指 Offer 34. 二叉树中和为某一值的路径 中等 目标和剪枝加回溯