**source:**https://leetcode.com/problems/path-sum-ii**C/C++**

**Solution to LeetCode**problem

**113**.

**Path Sum II**.

## Problem

Given the `root`

of a binary tree and an integer `targetSum`

, return *all root-to-leaf paths where the sum of the node values in the path equals targetSum. Each path should be returned as a list of the node values, not 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.

## Examples

**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 equals targetSum:

5 + 4 + 11 + 2 = 22

5 + 8 + 4 + 5 = 22

**Example 2:**

Input:root = [1,2,3], targetSum = 5

Output:[]

**Example 3:**

Input:root = [1,2], targetSum = 0

Output:[]

## Constraints

- The number of nodes in the tree is in the range
`[0, 5000]`

. `-1000 <= Node.val <= 1000`

`-1000 <= targetSum <= 1000`

## Solution

We will use recursion to perform a DFS (Depth First Search), at every node we will keep the sum (previous node’ values plus current node). Once the node doesn’t have children (left and right) it means we are at the end (leaf), and if the sum is equal to the target, then we have found a path.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

/**
* 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 {
private:
vector<vector<int>> result;
void exploreNode(TreeNode* node, vector<int> path, int sum, int *target) {
if (!node)
return;
path.push_back(node->val);
if (!node->left && !node->right) {
if (sum + node->val == *target)
result.push_back(path);
return;
}
exploreNode(node->left, path, sum + node->val, target);
exploreNode(node->right, path, sum + node->val, target);
}
public:
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
exploreNode(root, {}, 0, &targetSum);
return result;
}
};