113. Path Sum II

Question Given the root of a binary tree and an integer targetSum, it returns all paths from the root to a leaf where the sum of the values ​​of the nodes in the path equals targetSum. Each path should be returned as a list of node values, not as node references. A root-to-leaf path is a path starting from the root and ending at any leaf node. A leaf is a node with no children. Example 1: Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 Output: [[5,4,11,2],[5,8,4,5]] Explanation: There are two paths whose sum is equal to targetSum: 5 + 4 + 11 + 2 = 22 5 + 8 + 4 + 5 = 22 Example 2: Input: root = [1,2,3], target sum = 5 Output: [] Example 3: Input: root = [1,2], targetSum = 0 Output: [] Solution class Solution { public: vector> ans; vector path; void dfs(TreeNode* root, int current, int target) { if(!root) { return; } current += root->val; path.push_back(root->val); // When we reach at leaf node, we have to check if current sum is equal to target if(current == target && !root->left && !root->right) { ans.push_back(path); } dfs(root->left, current, target); dfs(root->right, current, target); path.pop_back(); } vector> pathSum(TreeNode* root, int targetSum) { dfs(root, 0, targetSum); return ans; } };