leetcode 129. 求根节点到叶节点数字之和

这篇具有很好参考价值的文章主要介绍了leetcode 129. 求根节点到叶节点数字之和。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目

给你一个二叉树的根节点 root ,树中每个节点都存放有一个 0 到 9 之间的数字。
每条从根节点到叶节点的路径都代表一个数字:

例如,从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。
计算从根节点到叶节点生成的 所有数字之和 。

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

示例 1:
leetcode 129. 求根节点到叶节点数字之和
输入:root = [1,2,3]
输出:25
解释:
从根到叶子节点路径 1->2 代表数字 12
从根到叶子节点路径 1->3 代表数字 13
因此,数字总和 = 12 + 13 = 25

示例 2:

leetcode 129. 求根节点到叶节点数字之和

输入:root = [4,9,0,5,1]
输出:1026
解释:
从根到叶子节点路径 4->9->5 代表数字 495
从根到叶子节点路径 4->9->1 代表数字 491
从根到叶子节点路径 4->0 代表数字 40
因此,数字总和 = 495 + 491 + 40 = 1026

提示:
树中节点的数目在范围 [1, 1000] 内
0 <= Node.val <= 9
树的深度不超过 10

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/sum-root-to-leaf-numbers
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。文章来源地址https://www.toymoban.com/news/detail-422389.html

题解思路

  • 分情况讨论递归,如果为空返回0,如果是叶子节点,返回当前的数乘10+当前节点的值。
  • 如果左右都不为空,返回dfs(left)+dfs(right)

代码

/**
 * 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:

    int dfs(TreeNode *root ,int prefix)
    {
        if(root==nullptr)
        {
            return 0;
        }
        prefix = root->val + prefix*10;
        if(root->left==nullptr && root->right==nullptr)
        {
            return prefix;
        }else{
            return dfs(root->left,prefix) + dfs(root->right,prefix);
        }
    }

    int sumNumbers(TreeNode* root) {
        return dfs(root, 0);
    }
};

到了这里,关于leetcode 129. 求根节点到叶节点数字之和的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • Leetcode129. 求根到叶子节点数字之和

    力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 给你一个二叉树的根节点  root  ,树中每个节点都存放有一个  0  到  9  之间的数字。 每条从根节点到叶节点的路径都代表一个数字: 例如,从根节点到叶子节点的路径  1 - 2 - 3  表示数字  123  。 计算从根节点到叶节

    2024年02月09日
    浏览(37)
  • 代码随想录额外题目| 二叉树 ●129求根到叶数字之和 ●1382二叉树变平衡●100相同的树

    #129求根到叶数字之和 回溯放进vector,然后从后往前拿,乘1 10 100 ... 很基础的回溯 my code: 随想录跟我思路差不多,但这两个是放globa的:int result; vectorint path; 最近总觉得global不安全不想放  #1382二叉树变平衡 本来遇到这种会换root的就头疼,然后看了眼随想录,是要先变成

    2024年02月14日
    浏览(34)
  • 面试算法49:从根节点到叶节点的路径数字之和

    在一棵二叉树中所有节点都在0~9的范围之内,从根节点到叶节点的路径表示一个数字。求二叉树中所有路径表示的数字之和。例如,图8.4的二叉树有3条从根节点到叶节点的路径,它们分别表示数字395、391和302,这3个数字之和是1088。 首先考虑如何计算路径表示的数字。顺着

    2024年02月06日
    浏览(40)
  • leetcode 1022.从根到叶的二进制数之和

    🌟 leetcode链接:https://leetcode.cn/problems/sum-of-root-to-leaf-binary-numbers/description/ 代码: 递归展开图:

    2024年02月10日
    浏览(33)
  • ​LeetCode解法汇总1080. 根到叶路径上的不足节点

    https://github.com/September26/java-algorithms 给你二叉树的根节点  root  和一个整数  limit  ,请你同时删除树中所有  不足节点  ,并返回最终二叉树的根节点。 假如通过节点  node  的每种可能的 “根-叶” 路径上值的总和全都小于给定的  limit ,则该节点被称之为  不足节点 

    2024年02月06日
    浏览(36)
  • DFS | 从根到叶的二进制数之和【附递归展开图】

    👉 力扣原题链接 首先我们来分析一下本题的思路 题目说到要求解每一条路径上的结点数字之和,但是本题并不是就简单的累加,而是要结合二进制的知识 对于每一条从根到叶的路径都代表一个从最高有效位开始的二进制数,要注意的是这个 最高有效位 ,也就是说越往下走

    2023年04月08日
    浏览(80)
  • 面试算法50:向下的路径节点值之和

    给定一棵二叉树和一个值sum,求二叉树中节点值之和等于sum的路径的数目。路径的定义为二叉树中顺着指向子节点的指针向下移动所经过的节点,但不一定从根节点开始,也不一定到叶节点结束。例如,在如图8.5所示中的二叉树中有两条路径的节点值之和等于8,其中,第1条

    2024年02月05日
    浏览(30)
  • n个节点互异的拉格朗日插值基函数之和等于一证明

     拉格朗日插值公式   要证明的 ,其左边拉格朗日基函数的的,也就是说方程用来插值的每个离散点都是,那么对于每个点插入点都满足。那么显然,不考虑其他性质,Ln拉格朗日插值公式是一个n-1次多项式,x最高次数是n个插值点的数目减一,但是它经过n个值为1的点,也就

    2024年02月11日
    浏览(42)
  • Brandes算法计算无向图节点最短路径之和-Java代码实现

            Brandes算法是一种经典的计算中介中心性的算法,它通过计算节点对之间的最短路径数量来评估节点的中介中心性。在复杂网络分析中,中介中心性是一种常用的指标,用于衡量节点在网络中的重要性程度。中介中心性越高的节点往往具有更大的影响力,可能成为

    2024年04月23日
    浏览(30)
  • 【算法】排序+双指针——leetcode三数之和、四数之和

    三数之和 (1)排序+双指针   算法思路: 和之前的两数之和类似,我们对暴力枚举进行了一些优化,利用了 排序+双指针 的思路:   我们先排序,然后固定⼀个数 a ,接着我们就可以在这个数后面的区间内,使用之前两数之和使用的算法,快速找到两个数之和和固定的

    2024年02月13日
    浏览(53)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包