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的路徑個數(shù)震蒋，路徑不一定是root to leaf, 但是必須是從上到下的宿稀。注意看一開始的錯誤解法以舒。
submit 1 : int基本類型參數(shù)傳入的是值，一旦傳入是不會像傳入引用類型的地址值一樣劈榨， 在函數(shù)運行過程中地址所指向的值會改變的啥酱。所以你的res = 0傳到函數(shù)里挡爵，res的值永遠(yuǎn)不會改變姆泻，一直是0.
submit 2 : 邊界條件錯誤， for循環(huán)執(zhí)行的條件是邊界條件為true,跟while一樣硼补。所以這里你表達(dá)的意思應(yīng)該是i >= 0,而不是i== 0, 后者作為邊界條件時for循環(huán)根本不會執(zhí)行驮肉。
/**
* 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;
}
}
