# 113. Path Sum II

### Leetcode

<https://leetcode.com/problems/path-sum-ii/>

### 題目

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.

&#x20;

**Example 1:**

![](https://assets.leetcode.com/uploads/2021/01/18/pathsumii1.jpg)

```
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:**

![](https://assets.leetcode.com/uploads/2021/01/18/pathsum2.jpg)

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

**Example 3:**

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

### 解答 <a href="#ti-jie" id="ti-jie"></a>

* **方法一**

Recursion

```
var pathSum = function(root, targetSum) {
    if (!root) return [];
    
    const res = [];
    
    const helper = (node, remain, arr) => {
        const nodeVal = node.val;
        remain = remain - nodeVal;
        const nextArr = [...arr, nodeVal];
        
        if (!node.left && !node.right) {
            if (remain === 0) res.push(nextArr);
        }
        if (node.left) {
            helper(node.left, remain, nextArr)
        }
        if (node.right) {
            helper(node.right, remain, nextArr)
        }
    }
    
    helper(root, targetSum, []);
    return res;
};
```

Runtime: 72 ms, faster than 95.87% of JavaScript online submissions for Path Sum II.

Memory Usage: 54.3 MB, less than 18.88% of JavaScript online submissions for Path Sum II.

* **方法二**

Iteration

```
var pathSum = function(root, targetSum) {
    if (!root) return [];
    
    const res = [];
    const queue = [{
        node: root,
        remain: targetSum,
        arr: []
    }];
    while (queue.length) {
        const curr = queue.shift();
        const node = curr.node;
        const nodeVal = node.val;
        const remain = curr.remain - nodeVal;
        const nextArr = [...curr.arr, nodeVal];
        
        if (!node.left && !node.right) {
            if (remain === 0) res.push(nextArr);
        }
        if (node.left) {
            queue.push({
                node: node.left,
                remain,
                arr: nextArr
            })
        }
        if (node.right) {
            queue.push({
                node: node.right,
                remain,
                arr: nextArr
            })
        }
    }
    
    return res;
};
```

Runtime: 118 ms, faster than 45.43% of JavaScript online submissions for Path Sum II.

Memory Usage: 49 MB, less than 50.15% of JavaScript online submissions for Path Sum II.
