本文主要是介绍【leetcode热题】求根到叶子节点数字之和,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
- 难度: 中等
- 通过率: 40.6%
- 题目链接:. - 力扣(LeetCode)
题目描述
给定一个二叉树,它的每个结点都存放一个 0-9
的数字,每条从根到叶子节点的路径都代表一个数字。
例如,从根到叶子节点路径 1->2->3
代表数字 123
。
计算从根到叶子节点生成的所有数字之和。
说明: 叶子节点是指没有子节点的节点。
示例 1:
输入: [1,2,3]1/ \2 3 输出: 25 解释: 从根到叶子节点路径1->2
代表数字12
. 从根到叶子节点路径1->3
代表数字13
. 因此,数字总和 = 12 + 13 =25
.
示例 2:
输入: [4,9,0,5,1]4/ \9 0/ \ 5 1 输出: 1026 解释: 从根到叶子节点路径4->9->5
代表数字 495. 从根到叶子节点路径4->9->1
代表数字 491. 从根到叶子节点路径4->0
代表数字 40. 因此,数字总和 = 495 + 491 + 40 =1026
.
解法:
深度优先遍历。
class Solution:def sumNumbers(self, root: TreeNode) -> int:result = 0def dfs(node, num):nonlocal resultif not node:returnnum = num * 10 + node.valif (node.left is None) and (node.right is None):result += numreturndfs(node.left, num)dfs(node.right, num)dfs(root, 0)return result
这篇关于【leetcode热题】求根到叶子节点数字之和的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!