---
# System prepended metadata

title: LC 113. Path Sum II
tags: [Binary Tree, medium, leedcode, c++]

---

# LC 113. Path Sum II

### [Problem link](https://leetcode.com/problems/path-sum-ii/)

###### tags: `leedcode` `medium` `c++` `Binary Tree`

Given the <code>root</code> of a binary tree and an integer <code>targetSum</code>, return all  **root-to-leaf**  paths where the sum of the node values in the path equals <code>targetSum</code>. 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.

**Example 1:** 
<img alt="" src="https://assets.leetcode.com/uploads/2021/01/18/pathsumii1.jpg" style="width: 500px; height: 356px;" />
```
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:** 
<img alt="" src="https://assets.leetcode.com/uploads/2021/01/18/pathsum2.jpg" style="width: 212px; height: 181px;" />
```
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 <code>[0, 5000]</code>.
- <code>-1000 <= Node.val <= 1000</code>
- <code>-1000 <= targetSum <= 1000</code>

## Solution 1
#### C++
```cpp=
class Solution {
public:
    vector<vector<int>> res;

    void traversal(TreeNode *node, vector<int> path, int sum) {
        path.push_back(node->val);
        if (node->left == nullptr && node->right == nullptr && sum == node->val) {
            res.push_back(path);
        }
        if (node->left) {
            traversal(node->left, path, sum - node->val);
        }
        if (node->right) {
            traversal(node->right, path, sum - node->val);
        }
    }

    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        vector<int> path;
        if (root != nullptr) {
            traversal(root, path, targetSum);
        }
        return res;
    }
};
```

>### Complexity
>n = The number of nodes in the tree
>|             | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1  | O(n)            | O(1)             |

## Note
x
