# 112. Path Sum

### Leetcode

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

### 題目

Given the `root` of a binary tree and an integer `targetSum`, return `true` if the tree has a **root-to-leaf** path such that adding up all the values along the path equals `targetSum`.

A **leaf** is a node with no children.

&#x20;

**Example 1:**

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

```
Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true
Explanation: The root-to-leaf path with the target sum is shown.
```

**Example 2:**

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

```
Input: root = [1,2,3], targetSum = 5
Output: false
Explanation: There two root-to-leaf paths in the tree:
(1 --> 2): The sum is 3.
(1 --> 3): The sum is 4.
There is no root-to-leaf path with sum = 5.
```

**Example 3:**

```
Input: root = [], targetSum = 0
Output: false
Explanation: Since the tree is empty, there are no root-to-leaf paths.
```

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

* **方法一**

Recursion

```
var hasPathSum = function(root, targetSum) {    
    if (!root) return false;
    const val = targetSum - root.val;

    if (!root.left && !root.right) {
        return val === 0;
    }
    return hasPathSum(root.left, val) || hasPathSum(root.right, val);
};
```

Runtime: 79 ms, faster than 80.83% of JavaScript online submissions for Path Sum.

Memory Usage: 45.7 MB, less than 40.85% of JavaScript online submissions for Path Sum.

* **方法二**

Iteration

```
var hasPathSum = function(root, targetSum) {
    if (root === null) return false;
    
    const res = [];
    const queue = [{
        val: targetSum - root.val,
        node: root
    }];
    while (queue.length) {
        const curr = queue.shift();        
        const val = curr.val;
        const node = curr.node;
        
        if (!node.left && !node.right) {
            if (val === 0) return true;
        }
        if (node.left) {
            queue.push({
                val: val - node.left.val,
                node: node.left
            })
        }
        if (node.right) {
            queue.push({
                val: val - node.right.val,
                node: node.right
            })
        }
    }
    
    return false;
};
```

Runtime: 96 ms, faster than 58.14% of JavaScript online submissions for Path Sum.

Memory Usage: 47 MB, less than 5.28% of JavaScript online submissions for Path Sum.
