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

【LetMeFly】129.求根节点到叶节点数字之和

力扣题目链接:https://leetcode.cn/problems/sum-root-to-leaf-numbers/

给你一个二叉树的根节点 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

方法一:BFS

这道题类似LeetCode 112.路径总和,直接进行一次遍历并修改原节点的值即可。

可参考题解https://blog.letmefly.xyz/2022/07/11/LeetCode 0112.路径总和/

  • 时间复杂度$O(n)$,其中$n$是二叉树节点的个数
  • 空间复杂度$O(n)$

AC代码

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
int sumNumbers(TreeNode* root) {
int ans = 0;
queue<TreeNode*> q;
q.push(root); // root 非空
while (q.size()) {
TreeNode* p = q.front();
q.pop();
if (!p->left && !p->right) {
ans += p->val;
continue;
}
p->val *= 10;
if (p->left) {
p->left->val += p->val;
q.push(p->left);
}
if (p->right) {
p->right->val += p->val;
q.push(p->right);
}
}
return ans;
}
};

同步发文于CSDN,原创不易,转载请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/125928616


129.求根节点到叶节点数字之和
https://blog.letmefly.xyz/2022/07/22/LeetCode 0129.求根节点到叶节点数字之和/
作者
Tisfy
发布于
2022年7月22日
许可协议