【LeetCode】路径总和 III

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。

路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

示例 1：

输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条，如图所示。

示例 2：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：3

提示:

二叉树的节点个数的范围是 [0,1000]
-10^9 <= Node.val <= 10^9
-1000 <= targetSum <= 1000

#include <stdio.h>
#include <stdlib.h>

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     long long val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

// 辅助函数：计算从当前节点开始的路径和等于 targetSum 的路径数量
long long helper(struct TreeNode* root, long long targetSum, long long curSum) {
    if (root == NULL) return 0;
    curSum += root->val;
    // 如果当前路径和等于 targetSum，计为一条路径
    long long count = (curSum == targetSum)? 1 : 0;
    // 继续在左右子树中寻找满足条件的路径
    count += helper(root->left, targetSum, curSum);
    count += helper(root->right, targetSum, curSum);
    return count;
}

// 主函数：计算二叉树中节点值之和等于 targetSum 的路径的数目
long long pathSum(struct TreeNode* root, long long targetSum) {
    if (root == NULL) return 0;
    // 从当前节点开始的路径数量
    long long fromRoot = helper(root, targetSum, 0);
    // 递归计算左子树和右子树的路径数量
    long long fromLeft = pathSum(root->left, targetSum);
    long long fromRight = pathSum(root->right, targetSum);
    // 总路径数量为从根节点开始的路径数量加上左右子树的路径数量
    return fromRoot + fromLeft + fromRight;
}