题目
解题思路
- 从每个节点开始向子节点遍历累加,当前达到目标值是结果加1;
- 方法一递归调用方法一;
- 方法二以当前节点的值为起始累加,符合结果则加1;
代码展示
class Solution {
int ans = 0;
int target;
public int pathSum(TreeNode root, int targetSum) {
target = targetSum;
dfs1(root);
return ans;
}
public void dfs1(TreeNode root){
if(root == null){
return;
}
dfs2(root,root.val);
dfs1(root.left);
dfs1(root.right);
}
public void dfs2(TreeNode root, long val){
if(val == target) {
ans++;
}
//不用else if避免存在先+后-或先-后+的情况,所以只要还存在子节点就需要遍历
if (root.left != null) {
dfs2(root.left, val + root.left.val);
}
if(root.right != null){
dfs2(root.right, val + root.right.val);
}
}
}