# 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++

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