> For the complete documentation index, see [llms.txt](https://cai-sen-se.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cai-sen-se.gitbook.io/leetcode/1-200/112.-lu-jing-zong-he.md).

# 112. 路径总和

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

## 解法一：dfs递归

递归左右子树，每次减去当前节点值

```python
class Solution:
    def hasPathSum(self, root: TreeNode, sum: int) -> bool:
        if not root:    #空节点
            return True if sum == 0 else False    #sum为0才正确，大于或小于0都不正确
        if sum < 0:
            return False
        return self.hasPathSum(root.left, sum-root.val) or self.hasPathSum(root.right, sum-root.val)
```

但是这种写法对于root为空且sum为0的case无法通过，因此改变判断时机，在叶节点而不是空节点才判断sum是否为0

而且sum<0就判否也不对，因为节点值可能为负

```python
class Solution:
    def hasPathSum(self, root: TreeNode, sum: int) -> bool:       
        if not root:    #空节点
            return False             
        if not root.left and not root.right:    #叶节点
            return sum-root.val == 0
        #对左右子树递归
        return self.hasPathSum(root.left, sum-root.val) or self.hasPathSum(root.right, sum-root.val)
```