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 pathSum(TreeNode root, int targetSum) {
if(root == null) {
return 0;
}
ArrayDeque<TreeNode> queue = new ArrayDeque<>();
queue.offer(root);
int total = 0;
while(!queue.isEmpty()) {
TreeNode node = queue.poll();
total += dfs(node, 0, targetSum);
if(node.left != null) {
queue.offer(node.left);
}
if(node.right != null) {
queue.offer(node.right);
}
}
return total;
}
private int dfs(TreeNode node, long curSum, int targetSum) {
if(node == null) return 0;
curSum += node.val;
int count = 0;
if(curSum == targetSum) {
count ++;
}
count += dfs(node.left, curSum, targetSum);
count += dfs(node.right, curSum, targetSum);
return count;
}
}
|