算法思路

该题是路径总和系列第三题，基本算法思路框架与 LeetCode 112. 路径总和 和 LeetCode 113. 路径总和 II 相同。但是该题中对合法路径的要求是路径不需要从根节点开始，也不需要在叶子节点结束。所以我们可以枚举每个结点作为起点，同时在判断路径总和是否等于目标值时并不需要要求该点为叶子节点。

C ++代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int res;
    int s;
    int pathSum(TreeNode* root, int sum) {
        if (!root) return 0;
        s = sum;
        dfs(root, 0);
        if (root -> left) pathSum(root -> left, sum); //不一定是从根节点开始
        if (root -> right) pathSum(root -> right, sum);
        return res;
    }

    void dfs(TreeNode* u, int sum)
    {
        sum += u -> val;
        if (s == sum) res ++; //路径不一定是叶节点结束
        if (!u -> left && !u -> right) return;
        if (u -> left) dfs(u -> left, sum);
        if (u -> right) dfs(u -> right, sum);
    }
};