Path Sum Iii - Leetcode Solution

Problem Statement: You are given a binary tree in which each node contains an integer value. Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

Solution: The problem can be approached using the concept of recursion. For each node, we can calculate the sum of all the paths that start at that node and reach any of its descendants. To do this, we need to consider two cases:

1. Include the current node in the path
2. Exclude the current node from the path If we include the current node in the path, then we need to pass the remaining sum (sum - node.val) to its children for further processing. If we exclude the current node from the path, then we just need to pass the original sum to its children.

We can implement this using a recursive function that takes the current node, the target sum, and the current sum as input. At each iteration, we check if the current sum equals the target sum. If yes, we increment the counter for the number of paths. Then, we process the left and right children of the current node using the above logic.

Code:

class Solution:
    def pathSum(self, root: TreeNode, sum: int) -> int:
        self.count = 0
        self.dfs(root, sum, [])
        return self.count
        
    def dfs(self, node, target, path):
        if node is None:
            return
        path.append(node.val)
        curr_sum = 0
        for i in range(len(path)-1, -1, -1):
            curr_sum += path[i]
            if curr_sum == target:
                self.count += 1
        self.dfs(node.left, target, path)
        self.dfs(node.right, target, path)
        path.pop()
        

Explanation: In the code above, we have defined a recursive function called dfs that takes three arguments:

1. node - the current node being processed
2. target - the target sum
3. path - a list of the values in the path from the root to the current node

We initialize the count of paths to 0 and call the dfs function with the root node, target sum, and an empty path.

In the dfs function, we first check if the current node is None, in which case we return. Otherwise, we add the current node's value to the path and initialize a variable called curr_sum to 0. We then loop through the path list from the end to the start and calculate the sum of all the values in the path from the current node to any of its ancestors. If this sum equals the target sum, we increment the counter for the number of paths.

We then recursively call the dfs function with the left child and right child of the current node, passing the target sum and the current path. After processing the children, we remove the current node's value from the path list to backtrack and explore other paths.

At the end of the recursion, we return the count of paths.

1