LeetCode 437. Path Sum III

题目

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);
}