# \[112]\[简单]\[BFS]\[DFS] 路径总和

## 题目描述

[112. 路径总和](https://leetcode-cn.com/problems/path-sum/)

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

说明: 叶子节点是指没有子节点的节点。

示例:

```
给定如下二叉树，以及目标和 sum = 22，

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1
返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
```

## 解题思路

### BFS

比较直接的思路是广度优先搜索. 结合**队列**, 从**根节点**开始, 搜索这个结点连接的所有子节点, 将子节点, 以及到此子节点为止路径之和压入到队列当中. 然后从队列中按照先入先出的原则依次取出节点, 同上所有子节点并压入队列, 不断循环, 直到遇到叶子结点且此时路径和为指定的`sum`值, 返回`True`, 否则直到队列为空终止, 并返回`False`.

```python
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def hasPathSum(self, root: TreeNode, sum: int) -> bool:
        if not root:
            return False

        queue = collections.deque([(root, root.val)])
        while queue:
            cur_node, cur_val = queue.popleft()
            if cur_node.left is None and cur_node.right is None:
                if cur_val == sum:
                    return True

            if cur_node.left:
                queue.append((cur_node.left, cur_val + cur_node.left.val))
            if cur_node.right:
                queue.append((cur_node.right, cur_val + cur_node.right.val))
        return False
```

### DFS

使用DFS思路绕一些, 需要通过递归实现. 首先, 我们得沿着一条路走到黑, 父节点将问题交给子节点时, 问题就转换成了**以该子节点为根节点的二叉树, 是否存在从根节点到叶子结点的路径和为`sum-parnet.value`**. 其中对于整个树的根节点来说就是指定的目标和, `parnet.value`对于整个树的根节点来说是根节点的值. 按照这个思路递归下去, 遇到下面两种情况返回:

* root为None, 说明其父节点为叶子结点, 这条路径无法满足, 返回False
* root为叶子节点且值正好等于剩余的`sum`值, 返回True

代码如下:

```python
class Solution:
    def hasPathSum(self, root: TreeNode, sum: int) -> bool:
        if root is None:
            return False

        if root.left is None and root.right is None and root.val == sum:
            return True

        return self.hasPathSum(root.left, sum - root.val) or self.hasPathSum(root.right, sum - root.val)
```