写点什么

每日一题:LeetCode-129. 求根节点到叶节点数字之和

作者:半亩房顶
  • 2023-12-11
    北京
  • 本文字数:712 字

    阅读完需:约 2 分钟

每日一题:LeetCode-129. 求根节点到叶节点数字之和

刷题使我快乐,满脸开心.jpg


题目

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


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


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


示例 1:



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


示例 2:



输入: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

思路

这道题其实就是一个DFS,从根往下遍历子节点,找到叶子节点时即可计入一个数字,加和即可~

代码

func sumNumbers(root *TreeNode) int {    sum := 0    var findSum func(*TreeNode, int)    findSum = func(root *TreeNode, temp int) {        temp = temp*10 + root.Val        if root.Right == nil && root.Left == nil {            sum += temp        }        if root.Left != nil {            findSum(root.Left, temp)        }        if root.Right != nil {            findSum(root.Right, temp)        }    }    findSum(root, 0)    return sum}
复制代码



欢迎关注公众号查看更多题目~


发布于: 刚刚阅读数: 3
用户头像

半亩房顶

关注

人生那么长,能写多少bug? 2018-11-16 加入

我希望,自己永远是自己。我希望,远离bug。

评论

发布
暂无评论
每日一题:LeetCode-129. 求根节点到叶节点数字之和_面试_半亩房顶_InfoQ写作社区