### 437. Path Sum III



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


难度:
Easy

思路：




```python
class Solution(object):
    def pathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: int
        """
        if not root:
            return 0
        res = self.auxPathSum(root, sum)
        res += self.pathSum(root.left, sum)
        res += self.pathSum(root.right, sum)
        return res
    def auxPathSum(self, root, sum):
        if not root:
            return 0
        if sum == root.val:
            # 因为可能有负值, 所以sum为0也会有解, 必须加上
            return 1 + self.auxPathSum(root.left, 0) + self.auxPathSum(root.right, 0) 
        else:
            return self.auxPathSum(root.left, sum - root.val) + self.auxPathSum(root.right, sum - root.val)
```