# 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


Solution:

Recursion, add a helper function that counts paths starting from a node

/**
* 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 pathSumHelper(TreeNode* root, int sum){
if(root == NULL) return 0;
return (root->val == sum) + pathSumHelper(root->left, sum-root->val) +pathSumHelper(root->right, sum-root->val);

}

int pathSum(TreeNode* root, int sum) {
if(root == NULL) return 0;
return pathSumHelper(root, sum) + pathSum(root->left, sum) + pathSum(root->right, sum);
}
};
{"ft_lang_label":"__label__en","ft_lang_prob":0.599762,"math_prob":0.99514276,"size":1155,"snap":"2022-40-2023-06","text_gpt3_token_len":358,"char_repetition_ratio":0.1346655,"word_repetition_ratio":0.019512195,"special_character_ratio":0.36536798,"punctuation_ratio":0.19379845,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9944161,"pos_list":[0,1,2],"im_url_duplicate_count":[null,null,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2022-10-05T08:24:48Z\",\"WARC-Record-ID\":\"<urn:uuid:2828ad49-bdc0-420c-a2cd-ecc26f73bb0f>\",\"Content-Length\":\"12478\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:fd1ca99a-2b9e-467a-9f84-b18c48e8d42d>\",\"WARC-Concurrent-To\":\"<urn:uuid:d04cd3f5-739b-48d8-ae2e-0cfa38303e36>\",\"WARC-IP-Address\":\"185.199.111.153\",\"WARC-Target-URI\":\"https://jinshang.me/blog/437.-Path-Sum-III/\",\"WARC-Payload-Digest\":\"sha1:6T53PJGKINGZQHMONRVYG6B7XT7CRBGQ\",\"WARC-Block-Digest\":\"sha1:I5TTO4XI7P5DUME2SAKADW4FZPCD5BDI\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2022/CC-MAIN-2022-40/CC-MAIN-2022-40_segments_1664030337595.1_warc_CC-MAIN-20221005073953-20221005103953-00535.warc.gz\"}"}