剑指 Offer II 049. 从根节点到叶节点的路径数字之和
难度中等34
给定一个二叉树的根节点 root
,树中每个节点都存放有一个 0
到 9
之间的数字。
每条从根节点到叶节点的路径都代表一个数字:
- 例如,从根节点到叶节点的路径
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
从根到叶子节点路径4->9->1
代表数字 491 从根到叶子节点路径4->0
代表数字 40 因此,数字总和 = 495 + 491 + 40 =1026
提示:
- 树中节点的数目在范围
[1, 1000]
内 0 <= Node.val <= 9
- 树的深度不超过
10
【剑指offer|剑指 Offer II 049. 从根节点到叶节点的路径数字之和】注意:本题与主站 129 题相同: 力扣
文章图片
文章图片
/**
* 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 {
public int sumNumbers(TreeNode root) {
return dfs(root, 0);
}
public int dfs(TreeNode root, int prevSum) {
if(root == null) {
return 0;
}
int sum = prevSum * 10 + root.val;
if(root.left == null && root.right == null) {
return sum;
} else {
return dfs(root.left, sum) + dfs(root.right, sum);
}
}
}
推荐阅读
- 大数据|计算机科学领域 直接 间接_为什么计算机科学领域的女性很少()
- 软件测试|接口测试项目(非常值得练手)
- https|https加密的基本原理
- 分布式|SpringCloud Netflix-Hystix使用
- 笔记|高中毕业,经过半年培训后成功拿到了美团的offer
- 日常错误|postman能正常请求但java程序请求返回400
- ServletException: java.lang.ExceptionInInitializerError
- 微服务系列|微服务系列(Spring Cloud Alibaba 之 Nacos 集群搭建)
- 分布式|SpringCloud Netflix-Eureka使用