437. Path Sum III

# Easy

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.

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

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

Second Tab