# 113

Aug 4th, 2021
769
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
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), right(right) {}
10.  * };
11.  */
12. class Solution {
13. public:
14.     vector<vector<int>> res;
15.     vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
16.         vector<int> path;
17.         int currSum=0;
18.         dfs(root, path, currSum, targetSum);
19.         return res;
20.     }
21.
22.     void dfs(TreeNode* root, vector<int> &path, int currSum, int targetSum){
23.         if(!root) return;
24.         path.push_back(root->val);
25.         currSum += root->val;
26.         if(!(root->left) && !(root->right) && currSum == targetSum){
27.             res.push_back(path);
28.         }
29.         else{
30.             dfs(root->left, path, currSum, targetSum);
31.             dfs(root->right, path, currSum, targetSum);
32.         }
33.         currSum -= root->val;
34.         path.pop_back();
35.     }
36.
37. };