Easy
You are given a binary tree in which each node contains an integer value.
Find the number of paths that sum to a given value.
The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).
The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.
Example:
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
10
/ \
5 -3
/ \ \
3 2 11
/ \ \
3 -2 1
Return 3. The paths that sum to 8 are:
1. 5 -> 3
2. 5 -> 2 -> 1
3. -3 -> 11
这道题是要找到满足sum == target的路径个数，路径不一定是root to leaf, 但是必须是从上到下的。注意看一开始的错误解法。
submit 1 : int基本类型参数传入的是值，一旦传入是不会像传入引用类型的地址值一样， 在函数运行过程中地址所指向的值会改变的。所以你的res = 0传到函数里，res的值永远不会改变，一直是0.
image.png
submit 2 : 边界条件错误， for循环执行的条件是边界条件为true,跟while一样。所以这里你表达的意思应该是i >= 0,而不是i== 0, 后者作为边界条件时for循环根本不会执行。
53D7D469-5DB1-46DA-9151-9D35E1BC5AF2.png
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int pathSum(TreeNode root, int sum) {
List<Integer> path = new ArrayList<>();
return helper(root, path, sum);
}
private int helper(TreeNode root, List<Integer> path, int sum){
int res = 0;
if (root == null){
return res;
}
path.add(root.val);
int pathSum = 0;
for (int i = path.size() - 1; i >= 0; i--){
pathSum += path.get(i);
if (pathSum == sum){
res++;
}
}
res += helper(root.left, path, sum);
res += helper(root.right, path, sum);
path.remove(path.size() - 1);
return res;
}
}
