题目
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
解析
此题和之前的一道题类似，使用递归对其进行类加。要注意的时候在每次递归的时候需要保存上一次的累加结果，这样才可以分别进行判断。如下，
newPathArr: [10]
newPathArr: [15, 5]
newPathArr: [18, 8, 3]
// 依次类推...
代码（C）
void allPathSum(struct TreeNode* root, int sum, int* pathArr, int level,
int* count);
int pathSum(struct TreeNode* root, int sum) {
int count = 0;
allPathSum(root, sum, NULL, 1, &count);
return count;
}
void allPathSum(struct TreeNode* root, int sum, int* pathArr, int level,
int* count) {
if (!root)
return ;
int* newPathArr = (int*)malloc(level * sizeof(int));
int i = 0;
for (i = 0; i < level - 1; ++i)
newPathArr[i] = pathArr[i] + root->val;
newPathArr[i] = root->val;
for (i = 0; i < level; ++i) {
if (newPathArr[i] == sum)
(*count) += 1;
}
allPathSum(root->left, sum, newPathArr, level + 1, count);
allPathSum(root->right, sum, newPathArr, level + 1, count);
free(newPathArr);
}
