LeetCode257. 二叉树的所有路径

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

写在前面:

题目链接:LeetCode257. 二叉树的所有路径
题目难度:简单
编程语言:C++

一、题目描述

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

叶子节点 是指没有子节点的节点。
LeetCode257. 二叉树的所有路径

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

示例 2 :

输入:root = [1]
输出:[“1”]

二、题目分析&解题思路

由于是从回溯法里找了一道题,那么就话不多说直接上回溯
如果之前没有了解过回溯的可以先看看回溯的思路:
LeetCode257. 二叉树的所有路径
如果还是不太理解的话,可以参考下面这篇博客:
LeetCode.46. 全排列(回溯法入门)

不过每个节点的值需要从 int 转到 string
刚开始不知道 C++ 里面有专门 Int To string 的方法(大傻子本人了)
然后自己啥没写,先自己手写了一个 Int To string 的方法,感觉太傻了,各位献丑了:

vector<string> vctMap = {"0","1","2","3","4","5","6","7","8","9"};
    string IntToStr(int val)
    {
        if(val >=0 && val < 10)
        {
            return vctMap[val];
        }
        else if(val>-10 && val <0)
        {
            val = -val;
            string strResult = "-" + vctMap[val];
            return strResult;
        }
        else 
        {
            bool isFushu = false;
            if(val < 0)
            {
                isFushu = true;
                val = -val;
            }
            //开始取每一位
            string strResult = "";
            while( val > 0)
            {
                int temp = val%10;
                strResult.insert(0,vctMap[temp]);
                val/=10;
            }
            if(isFushu)
            {
                strResult.insert(0, "-");
            }
            return strResult;
        }
    }

然后下面才是回溯的代码:

    //回溯函数
    void back(TreeNode* root, string strPath)
    {
        //终止条件
        if(root->left == nullptr && root->right == nullptr)
        {
            vctResult.push_back(strPath);
            return;
        }
        //不断向递归终止条件逼近
        //左
        if(root->left != nullptr)
        {
            string strTemp = "->"+IntToStr(root->left->val);
            strPath+=strTemp;
            back(root->left, strPath);
            //回溯 也就是把上一次的结果删除掉
            strPath.resize(strPath.size() - strTemp.size());
        }
        //右
        if(root->right != nullptr)
        {
            string strTemp = "->"+IntToStr(root->right->val);
            strPath+=strTemp;
            back(root->right, strPath);
            //回溯
            strPath.resize(strPath.size() - strTemp.size());
        }
        
    }

三、完整代码

class Solution {
public:
vector<string> vctResult;
string strPath = "";
vector<string> vctMap = {"0","1","2","3","4","5","6","7","8","9"};
public:
    //自己傻傻写的int to string 函数
    string IntToStr(int val)
    {
        if(val >=0 && val < 10)
        {
            return vctMap[val];
        }
        else if(val>-10 && val <0)
        {
            val = -val;
            string strResult = "-" + vctMap[val];
            return strResult;
        }
        else 
        {
            bool isFushu = false;
            if(val < 0)
            {
                isFushu = true;
                val = -val;
            }
            //开始取每一位
            string strResult = "";
            while( val > 0)
            {
                int temp = val%10;
                strResult.insert(0,vctMap[temp]);
                val/=10;
            }
            if(isFushu)
            {
                strResult.insert(0, "-");
            }
            return strResult;
        }
    }
    //回溯函数
    void back(TreeNode* root, string strPath)
    {
        //终止条件
        if(root->left == nullptr && root->right == nullptr)
        {
            vctResult.push_back(strPath);
            return;
        }
        //不断向递归终止条件逼近
        if(root->left != nullptr)
        {
        	//保存每个路径上的节点值
            string strTemp = "->"+IntToStr(root->left->val);
            strPath+=strTemp;
            back(root->left, strPath);
            //回溯
            strPath.resize(strPath.size() - strTemp.size());
        }
        if(root->right != nullptr)
        {
        	//保存每个路径上的节点值
            string strTemp = "->"+IntToStr(root->right->val);
            strPath+=strTemp;
            back(root->right, strPath);
            //回溯
            strPath.resize(strPath.size() - strTemp.size());
        }
        
    }
    vector<string> binaryTreePaths(TreeNode* root) {
        if(root == nullptr)
        {
            return vctResult;
        }
        else
        {
            //先开始把根节点加上
            strPath = IntToStr(root->val);
            back(root, strPath);
            return vctResult;
        }

    }
};

运行结果:
LeetCode257. 二叉树的所有路径
我们再使用c++ 自己的to_string 接口试试:

/**
 * 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> vctResult;
string strPath = "";
public:
    //回溯函数
    void back(TreeNode* root, string strPath)
    {
        //终止条件
        if(root->left == nullptr && root->right == nullptr)
        {
            vctResult.push_back(strPath);
            return;
        }
        //不断向递归终止条件逼近
        //向左
        if(root->left != nullptr)
        {
            string strTemp = "->"+to_string(root->left->val);
            strPath+=strTemp;
            back(root->left, strPath);
            //回溯 也就是把上次的结果删除掉
            strPath.resize(strPath.size() - strTemp.size());
        }
        //向右
        if(root->right != nullptr)
        {
            string strTemp = "->"+to_string(root->right->val);
            strPath+=strTemp;
            back(root->right, strPath);
            //回溯
            strPath.resize(strPath.size() - strTemp.size());
        }
        
    }
    vector<string> binaryTreePaths(TreeNode* root) {
        if(root == nullptr)
        {
            return vctResult;
        }
        else
        {
            //先开始把根节点加上
            strPath = to_string(root->val);
            back(root, strPath);
            return vctResult;
        }

    }
};

运行结果:
LeetCode257. 二叉树的所有路径文章来源地址https://www.toymoban.com/news/detail-495136.html

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

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

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

相关文章

  • 算法训练day17leetcode110平衡二叉树257二叉树的所有路径404左叶子之和

    https://www.bilibili.com/video/BV1GY4y1K7z8/?vd_source=8272bd48fee17396a4a1746c256ab0ae https://programmercarl.com/0404.%E5%B7%A6%E5%8F%B6%E5%AD%90%E4%B9%8B%E5%92%8C.html#%E6%80%9D%E8%B7%AF 采用后序递归遍历,比较左右子树的高度,相差小于等于1 前序,中左右,从根节点到叶子节点,会一直向下遍历下去,不会返回信

    2024年01月19日
    浏览(44)
  • 力扣 257. 二叉树的所有路径

    题目来源:https://leetcode.cn/problems/binary-tree-paths/description/    C++题解1:使用递归,声明了全局变量result,遇到叶子节点就将字符串添加到result中。 递归三步法: 1. 确认传入参数:当前节点+已有路径(字符串); 2. 确认终止条件:遇到叶子节点,即左右节点都为空时,将当前

    2024年02月11日
    浏览(36)
  • day17 | 110.平衡二叉树、 257. 二叉树的所有路径、 404.左叶子之和

    目录: 题目链接: https://leetcode.cn/problems/balanced-binary-tree/ https://leetcode.cn/problems/binary-tree-paths/ 110. 平衡二叉树 给定一个二叉树,判断它是否是高度平衡的二叉树。 本题中,一棵高度平衡二叉树定义为: 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。 示

    2024年02月08日
    浏览(42)
  • LeetCode刷题--- 二叉树的所有路径

    个人主页:元清加油_【C++】,【C语言】,【数据结构与算法】-CSDN博客 个人专栏 力扣递归算法题       【     】 【C++】                  【   】 数据结构与算法       【    】 前言:这个专栏主要讲述递归递归、搜索与回溯算法,所以下面题目主要也是这些算法做的

    2024年01月19日
    浏览(43)
  • 算法刷题Day 17 平衡二叉树+二叉树的所有路径+左叶子之和

    计算左右两棵子树的高度,如果有一个高度是-1(有一棵子树不平衡),直接返回-1,否则计算高度差,判断是否不平衡 使用 回溯 的方法,每次处理一个节点之前要把它push进table里,处理完之后又要把它pop出来 处理一个节点时,要判断它是否是左节点(需要父节点,可以通

    2024年02月15日
    浏览(43)
  • 二叉树题目:二叉树的中序遍历

    标题:二叉树的中序遍历 出处:94. 二叉树的中序遍历 3 级 要求 给你二叉树的根结点 root texttt{root} root ,返回其结点值的中序遍历。 示例 示例 1: 输入: root   =   [1,null,2,3] texttt{root = [1,null,2,3]} root = [1,null,2,3] 输出: [1,3,2] texttt{[1,3,2]} [1,3,2] 示例 2: 输入: root   =  

    2024年02月09日
    浏览(53)
  • 二叉树题目:二叉树的层序遍历 II

    标题:二叉树的层序遍历 II 出处:107. 二叉树的层序遍历 II 4 级 要求 给你二叉树的根结点 root texttt{root} root ,返回其结点值自底向上的层序遍历(即从左到右,按从叶结点所在层到根结点所在层逐层遍历)。 示例 示例 1: 输入: root   =   [3,9,20,null,null,15,7] texttt{root = [3

    2024年02月11日
    浏览(38)
  • 二叉树题目:二叉树的序列化与反序列化

    标题:二叉树的序列化与反序列化 出处:297. 二叉树的序列化与反序列化 8 级 要求 序列化是将一个数据结构或者对象转换为连续的比特位的操作,进而可以将转换后的数据存储在一个文件或者内存中,同时也可以通过网络传输到另一个计算机环境,采取相反方式重构得到原

    2024年01月23日
    浏览(44)
  • C++力扣题目104--二叉树的最大深度

    给定一个二叉树,找出其最大深度。 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。 说明: 叶子节点是指没有子节点的节点。 示例: 给定二叉树 [3,9,20,null,null,15,7], 返回它的最大深度 3 。 看完本篇可以一起做了如下两道题目: 104.二叉树的最大深度(opens n

    2024年01月16日
    浏览(65)
  • 【数据结构】二叉树的销毁 & 二叉树系列所有源代码(终章)

    目录 一,二叉树的销毁  二,二叉树系列所有源代码 BTee.h BTee.c Queue.h Queue.c 二叉树建好了,利用完了,也该把申请的动态内存空间给释放了,那要如何释放呢? 我们还是以这棵树为例, 要把这棵树销毁掉,其实就是把树上的结点全部释放掉 ,但是呢这个 释放的顺序挺讲究

    2024年02月08日
    浏览(47)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包