1
/**
2
 * Definition for a binary tree node.
3
 * struct TreeNode {
4
 * int val;
5
 * TreeNode *left;
6
 * TreeNode *right;
7
 * TreeNode() : val(0), left(nullptr), right(nullptr) {}
8
 * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9
 * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
10
 * right(right) {}
11
 * };
12
 */
13
class Solution {
14
 public:
15
  vector<vector<int>> v;
16
  void helper(vector<int> &t, int target, TreeNode *root) {
17
    if (root == NULL) {
18
      return;
19
    }
20
    if (root->left == NULL && root->right == NULL && target == root->val) {
21
      t.push_back(root->val);
22
      v.push_back(t);
23
      t.pop_back();
24
      return;
25
    }
26
    target = target - root->val;
27
    t.push_back(root->val);
28
    helper(t, target, root->left);
29
    helper(t, target, root->right);
30
    t.pop_back();
31

32
    // cout<<root->val<<" "<<target<<endl;
33
    return;
34
  }
35
  vector<vector<int>> pathSum(TreeNode *root, int targetSum) {
36
    vector<int> t;
37
    helper(t, targetSum, root);
38
    return v;
39
  }
40
};