> For the complete documentation index, see [llms.txt](https://r24zeng.gitbook.io/leetcode-notebook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://r24zeng.gitbook.io/leetcode-notebook/binary-search-and-tree/437.-path-sum-iii.md).

# 437. Path Sum III

\# Easy

{% hint style="info" %}
Very hard. Use two recursive. 

`dfs(root, sum)` return the count of path from root to current node.

`sumPath(root, sum)` return the count of path from any node to any node, including `dfs(root, sum)`'s result.
{% endhint %}

### Solution vedio link: <https://www.youtube.com/watch?v=NTyOEYYyv-o>

{% tabs %}
{% tab title="Python" %}

```python
class Solution:
    def pathSum(self, root: TreeNode, sum: int) -> int:
        # edge case
        if root == None:
            return 0
        
        return self.dfs(root, sum) + self.pathSum(root.left, sum) + self.pathSum(root.right, sum)
        
        
    # path sum from root to leave
    def dfs(self, root, sum):
        # stop condition
        if root == None:
            return 0

        # regular case
        count = 0
        if sum == root.val:
            count = count + 1
        count += self.dfs(root.left, sum-root.val)
        count += self.dfs(root.right, sum-root.val)
        
        return count
```

{% endtab %}

{% tab title="Second Tab" %}

{% endtab %}
{% endtabs %}