<p>Given the <code>root</code> of a binary tree and an integer <code>targetSum</code>, return <em>the number of paths where the sum of the values&nbsp;along the path equals</em>&nbsp;<code>targetSum</code>.</p>

<p>The path does not need to start or end at the root or a leaf, but it must go downwards (i.e., traveling only from parent nodes to child nodes).</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/04/09/pathsum3-1-tree.jpg" style="width: 450px; height: 386px;" />
<pre>
<strong>Input:</strong> root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
<strong>Output:</strong> 3
<strong>Explanation:</strong> The paths that sum to 8 are shown.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
<strong>Output:</strong> 3
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li>The number of nodes in the tree is in the range <code>[0, 1000]</code>.</li>
	<li><code>-10<sup>9</sup> &lt;= Node.val &lt;= 10<sup>9</sup></code></li>
	<li><code>-1000 &lt;= targetSum &lt;= 1000</code></li>
</ul>

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:

    vector<long long> findSum(TreeNode* root, int k, int &count){
        if(root == NULL) return {};

        vector<long long> left = findSum(root->left, k, count);
        vector<long long> right = findSum(root->right, k, count);

        vector<long long> ans;
        ans.push_back(root->val);

        for(int i=0;i<left.size();i++){
            ans.push_back(root->val + left[i]);
        }

        for(int i=0;i<right.size();i++){
            ans.push_back(root->val + right[i]);
        }

        for(int i=0;i<ans.size();i++){
            if(ans[i] == k){
                count++;
            }
        }

        return ans;
    }

    int pathSum(TreeNode* root, int k) {
        // 3, -2
        // 3, 6, 1, (5 ka left)

        // 1
        // 2, 3 (5 ka right)

        // 5, 8, 11, 6, 7, 8 (10 ka left)
        
        // 11
        // -3, 8 (10 ka right)

        // 10, 15, 18, 21, 16, 17, 18, 7, 18 (At 10)
        // vector<int> arr;
        int count = 0;

        findSum(root,k,count);

        return count;
    }
};
95963