DFS
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
29
30
31
32
33
| class Solution {
public int sumNumbers(TreeNode root) {
List<List<Integer>> resultList = new ArrayList<>();
List<Integer> pathNumList = new ArrayList<>();
dfs(resultList, pathNumList, root);
int sum = 0;
for (List<Integer> numList : resultList) {
int num = 0;
for (int n : numList) {
num = num * 10 + n;
}
sum += num;
}
return sum;
}
private void dfs(List<List<Integer>> resultList, List<Integer> pathNumList, TreeNode root) {
pathNumList.add(root.val);
if (root.left == null && root.right == null) {
resultList.add(new ArrayList<>(pathNumList));
}
if (root.left != null) {
dfs(resultList, pathNumList, root.left);
}
if (root.right != null) {
dfs(resultList, pathNumList, root.right);
}
pathNumList.remove(pathNumList.size() - 1);
}
}
|
DFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public int sumNumbers(TreeNode root) {
return dfs(root, 0);
}
private int dfs(TreeNode root, int preSum) {
if (root == null) {
return 0;
}
preSum = preSum * 10 + root.val;
if (root.left == null && root.right == null) {
return preSum;
} else {
return dfs(root.left, preSum) + dfs(root.right, preSum);
}
}
}
|
BFS
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) {
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int sum = 0;
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (node.left == null && node.right == null) {
sum += node.val;
continue;
}
if (node.left != null) {
node.left.val = node.val * 10 + node.left.val;
queue.offer(node.left);
}
if (node.right != null) {
node.right.val = node.val * 10 + node.right.val;
queue.offer(node.right);
}
}
return sum;
}
}
|
References
129. Sum Root to Leaf Numbers
剑指 Offer II 049. 从根节点到叶节点的路径数字之和