LeetCode_二叉树_DFS_中等_129.求根节点到叶节点数字之和

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

1.题目

给你一个二叉树的根节点 root ,树中每个节点都存放有一个 0 到 9 之间的数字。
每条从根节点到叶节点的路径都代表一个数字:例如,从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123。
计算从根节点到叶节点生成的所有数字之和 。

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

示例 1:

LeetCode_二叉树_DFS_中等_129.求根节点到叶节点数字之和

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

示例 2:

LeetCode_二叉树_DFS_中等_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

2.思路

(1)DFS

相关题目:
LeetCode_二叉树_中等_113.路径总和 II文章来源地址https://www.toymoban.com/news/detail-474612.html

3.代码实现(Java)

//思路1————DFS
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    
    StringBuilder builder = new StringBuilder();
    int res = 0;
    
    public int sumNumbers(TreeNode root) {
        dfs(root);
        return res;
    }
    
    private void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        builder.append(root.val);
        if (root.left == null && root.right == null) {
            res += Integer.parseInt(builder.toString());
        }
        dfs(root.left);
        dfs(root.right);
        builder.deleteCharAt(builder.length() - 1);
    }
}

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

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

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

相关文章

  • [力扣 129]求根节点到叶节点之和

    题目描述: 思路: 可以采用递归+回溯。递归访问左-右-根节点并记录路径。到叶节点后,计算数字并相加。 代码:

    2024年04月14日
    浏览(26)
  • Leetcode129. 求根到叶子节点数字之和

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

    2024年02月09日
    浏览(35)
  • 【LeetCode-中等题】199. 二叉树的右视图

    根 右 左 的顺序 取每层第一个被访问到的节点(depth == list.size())

    2024年02月10日
    浏览(34)
  • 【LeetCode-中等题】114. 二叉树展开为链表

    将左子树插入到右子树的地方 将原来的右子树接到左子树的最右边节点 考虑新的右子树的根节点,一直重复上边的过程,直到新的右子树为 null

    2024年02月10日
    浏览(35)
  • LeetCode算法二叉树—222. 完全二叉树的节点个数

    目录 222. 完全二叉树的节点个数 - 力扣(LeetCode) 代码: 运行结果:  给你一棵  完全二叉树  的根节点  root  ,求出该树的节点个数。 完全二叉树 的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集

    2024年02月07日
    浏览(42)
  • 每天一道leetcode:剑指 Offer 34. 二叉树中和为某一值的路径(中等&图论&深度优先遍历&递归)

    给你二叉树的根节点 root 和一个整数目标和 targetSum ,找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。 叶子节点 是指没有子节点的节点。 树中节点总数在范围 [0, 5000] 内 -1000 = Node.val = 1000 -1000 = targetSum = 1000 使用递归深度优先遍历,使用前序遍历,在遍历途

    2024年02月12日
    浏览(48)
  • 【完全二叉树节点数!】【深度优先】【广度优先】Leetcode 222 完全二叉树的节点个数

    ---------------🎈🎈题目链接🎈🎈------------------- 完全二叉树只有两种情况: 情况一:就是满二叉树, 情况二:最后一层叶子节点没有满。 对于情况一,可以直接用 2 ^ 树深度 - 1 来计算,注意这里根节点深度为1。 对于情况二,分别递归左孩子,和右孩子,递归到某一深度一

    2024年02月19日
    浏览(34)
  • 算法训练day16Leetcode104二叉树最大深度111二叉树最小深度222完全二叉树的节点个数

    https://www.bilibili.com/video/BV1Gd4y1V75u/?vd_source=8272bd48fee17396a4a1746c256ab0ae 用递归,但是什么顺序没想清楚 二叉树节点的深度:指从根节点到该节点的最长简单路径边的条数或者节点数(取决于深度从0开始还是从1开始) 二叉树节点的高度:指从该节点到叶子节点的最长简单路径边

    2024年01月16日
    浏览(43)
  • Java LeetCode篇-二叉树经典解法(实现:判断平衡二叉树、找两个节点最近的祖先等)

    🔥博客主页: 【 小扳_-CSDN博客】 ❤感谢大家点赞👍收藏⭐评论✍     文章目录         1.0 平衡二叉树         1.1 实现判断平衡二叉树的思路         1.2 代码实现判断平衡二叉树         2.0 二叉树的层序遍历         2.1 实现二叉树层序遍历的思路          2.2

    2024年02月05日
    浏览(49)
  • LeetCode 2641. 二叉树的堂兄弟节点 II:层序遍历并记下兄弟节点

    力扣题目链接:https://leetcode.cn/problems/cousins-in-binary-tree-ii/ 给你一棵二叉树的根  root  ,请你将每个节点的值替换成该节点的所有 堂兄弟节点值的和  。 如果两个节点在树中有相同的深度且它们的父节点不同,那么它们互为 堂兄弟  。 请你返回修改值之后,树的根   root

    2024年02月20日
    浏览(42)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包