Leetcode :257. 二叉树的所有路径(dfs || bfs）

最新推荐文章于 2025-05-29 15:02:38 发布

任老爸张

最新推荐文章于 2025-05-29 15:02:38 发布

阅读量174

点赞数

分类专栏： leetcode 文章标签：二叉树 dfs bfs 算法数据结构

本文链接：https://blog.csdn.net/stackempty2/article/details/108406200

版权

leetcode 专栏收录该内容

115 篇文章

订阅专栏

这道题目要求找到二叉树中从根节点到所有叶子节点的路径。通过深度优先搜索（DFS）或广度优先搜索（BFS）可以解决。示例输入是一个二叉树，输出是所有根到叶子节点的路径，如“1->2->5”，“1->3”。DFS解决方案通常更直接，而BFS虽然稍复杂，但避免了递归。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

二叉树的所有路径
给定一个二叉树，返回所有从根节点到叶子节点的路径。

说明: 叶子节点是指没有子节点的节点。

示例:

输入:

1
/
2 3

5

输出: [“1->2->5”, “1->3”]

解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3

这道题还是比较常规的深度优先遍历的，递归一手函数就ok了，或者用bfs，不过bfs还是略微有一点麻烦的，但是不需要递归，

class Solution {
public:
    void construct_paths(TreeNode* root, string path, vector<string>& paths) {
        if (root != nullptr) {
            path += to_string(root->val);
            if (root->left == nullptr && root->right == nullptr) {  // 当前节点是叶子节点
                paths.push_back(path);                              // 把路径加入到答案中
            } else {
                path += "->";  // 当前节点不是叶子节点，继续递归遍历
                construct_paths(root->left, path, paths);
                construct_paths(root->right, path, paths);
            }
        }
    }

    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> paths;
        construct_paths(root, "", paths);
        return paths;
    }
};