题目
给你一个二叉树的根节点 root ，树中每个节点都存放有一个
0 到 9 之间的数字。
每条从根节点到叶节点的路径都代表一个数字：
- 例如，从根节点到叶节点的路径
1 -> 2 -> 3 表示数字
123 。
计算从根节点到叶节点生成的 所有数字之和 。
叶节点 是指没有子节点的节点。
示例 1：
img
1
2
3
4
5
6
| 输入：root = [1,2,3]
输出：25
解释：
从根到叶子节点路径 1->2 代表数字 12
从根到叶子节点路径 1->3 代表数字 13
因此，数字总和 = 12 + 13 = 25
|
示例 2：
img
1
2
3
4
5
6
7
| 输入：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
题解
这题其实和112有点像来着。不过这里求根节点到叶节点所有数字之和，而且这个和比较特殊。
思路差不多，用dfs找到根节点，这里计算sum的时候，需要注意，按照题目要求sum = sum * 10 + root.val即可。这里因为路径之和可能会重复，那么我们用ArrayList保存数据即可。list里保存的是根节点到每个叶节点的数字之和，所以最后还要再加在一起。
时间复杂度100%，空间复杂度82%，可以说很棒了捏~(●ˇ∀ˇ●)
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
27
28
| class Solution {
public int sumNumbers(TreeNode root) {
if (root == null) {
return 0;
}
int res = 0;
ArrayList<Integer> sumList = new ArrayList<>();
dfs(root, sumList, res);
res = 0;
for (Integer sum : sumList) {
res += sum;
}
return res;
}
public void dfs(TreeNode root, ArrayList<Integer> sumList, int sum) {
if (root != null) {
if (root.right != null || root.left != null) {
sum = sum * 10 + root.val;
dfs(root.left, sumList, sum);
dfs(root.right, sumList, sum);
} else {
sum = sum * 10 + root.val;
sumList.add(sum);
}
}
}
}
|