LeetCode刷题--- 二叉树的所有路径

这篇具有很好参考价值的文章主要介绍了LeetCode刷题--- 二叉树的所有路径。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

个人主页:元清加油_【C++】,【C语言】,【数据结构与算法】-CSDN博客

个人专栏

力扣递归算法题       【     】
【C++】                  【   】
数据结构与算法       【    】


前言:这个专栏主要讲述递归递归、搜索与回溯算法,所以下面题目主要也是这些算法做的  

我讲述题目会把讲解部分分为3个部分:
1、题目解析

2、算法原理思路讲解

3、代码实现


二叉树的所有路径

题目链接:二叉树的所有路径

题目

给你一个二叉树的根节点 root ,按 任意顺序 ,返回所有从根节点到叶子节点的路径。

叶子节点 是指没有子节点的节点。

示例 1:

LeetCode刷题--- 二叉树的所有路径,力扣递归算法题,leetcode,算法文章来源地址https://www.toymoban.com/news/detail-804942.html

输入:root = [1,2,3,null,5]
输出:["1->2->5","1->3"]

示例 2:

输入:root = [1]
输出:["1"]

提示:

  • 树中节点的数目在范围 [1, 100] 内
  • -100 <= Node.val <= 10

解法

题目解析

题目意思很简单,给我们一颗二叉树,让我们返回二叉树所有的路径

例如:

LeetCode刷题--- 二叉树的所有路径,力扣递归算法题,leetcode,算法

输入:root = [1,2,3,null,5]
输出:["1->2->5","1->3"]

算法原理思路讲解   

算法思路
使⽤深度优先遍历(DFS)求解
路径以字符串形式存储,从根节点开始遍历,每次遍历时将当前节点的值加⼊到路径中,如果该节点为叶⼦节点,将路径存储到结果中。否则,将 "->" 加⼊到路径中并递归遍历该节点的左右⼦树。
定义⼀个结果数组,进⾏递归。递归具体实现⽅法如下:
  1. 如果当前节点不为空,就将当前节点的值加⼊路径 path 中,否则直接返回;
  2. 判断当前节点是否为叶⼦节点,如果是,则将当前路径加⼊到所有路径的存储数组 ret 中
  3. 否则,将当前节点值加上 "->" 作为路径的分隔符,继续递归遍历当前节点的左右⼦节点。


 代码实现 

  • 时间复杂度:O(N^2),其中 N 表示节点数目。在深度优先搜索中每个节点会被访问一次且只会被访问一次,每一次会对 path 变量进行拷贝构造,时间代价为 O(N),故时间复杂度为 O(N^2)。
  • 空间复杂度:O(N^2),其中 N 表示节点数目。除答案数组外我们需要考虑递归调用的栈空间。在最坏情况下,当二叉树中每个节点只有一个孩子节点时,即整棵二叉树呈一个链状,此时递归的层数为 NNN.
    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
     *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
     *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
     * };
     */
    class Solution 
    {
    public:
        vector<string> ret;
    
        void dfs(TreeNode* root , string path)
        {
            if (root != nullptr)
                path += to_string(root->val);
            else
                return ;
            
            if(root->left == nullptr && root->right == nullptr)
            {
                ret.push_back(path);
                return;
            }
            path += "->";
            if(root->left) dfs(root->left, path);
            if(root->right) dfs(root->right, path);
        }
    
        vector<string> binaryTreePaths(TreeNode* root) 
        {
            string path;
            if(root == nullptr) 
                return ret;
    
            dfs(root,path);
            return ret;
        }
    };

到了这里,关于LeetCode刷题--- 二叉树的所有路径的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包