---
description: '# Easy'
---

# 437. Path Sum III

{% hint style="info" %}
Very hard. Use two recursive.&#x20;

`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](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 %}

