Path Sum Iv - 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).

Example: Input: 10 /
5 -3 / \
3 2 11 / \
3 -2 1

Target Sum: 8

Output: 3

Explanation: The paths that sum to 8 are:

1. 5 -> 3
2. 5 -> 2 -> 1
3. -3 -> 11

Solution: To solve this problem, we can use a DFS approach. The idea is to traverse the entire binary tree and keep track of the current path sum at each node. At each node, we can check if the current path sum equals the target sum and increment a global count variable.

We also need to keep track of the current path values, so that we can remove the incorrect path values when we backtrack. We can use a list to store the current path values.

For each node, we can add its value to the current path list and update the current path sum. Then, we can check if the current path sum equals the target sum. If it does, we increment the global count variable.

We then recursively call the function for the left and right children of the node. After the left and right children have been processed, we need to remove the current node's value from the current path list and subtract it from the current path sum.

We need to initialize the global count to 0, and call the DFS function for the root node.

Here's the Python code for the solution:

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

The time complexity of this solution is O(n^2), where n is the number of nodes in the binary tree. This is because we are traversing the entire tree and, for each node, we are performing a linear scan of the current path list.

A better solution would be to use a hash table to store the number of times each path sum occurs from the root to the current node. The idea is to store the path sum along with its frequency in a hash table, and then for each node, we can subtract the target sum from the current path sum and check if the difference exists in the hash table. If it does, we can add the frequency of that sum to the global count variable.

Here's the optimized Python code for the solution:

class Solution:
    def pathSum(self, root: TreeNode, targetSum: int) -> int:
        self.count = 0
        prefixSum = defaultdict(int)
        prefixSum[0] = 1
        def dfs(node, pathSum):
            if not node: 
                return 
            pathSum += node.val
            if (pathSum - targetSum) in prefixSum:
                self.count += prefixSum[pathSum - targetSum]
            prefixSum[pathSum] += 1
            dfs(node.left, pathSum)
            dfs(node.right, pathSum)
            prefixSum[pathSum] -= 1
        dfs(root, 0)
        return self.count

The time complexity of the optimized solution is O(n), where n is the number of nodes in the binary tree. This is because we are traversing the entire tree only once, and the hash table operations can be considered constant time.

1