# \[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)
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://kerasnoone.gitbook.io/garnet/suan-fa/shu/112-lu-jing-zong-he.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.