Path Sum III.md

Path Sum III

Given the root of a binary tree and an integer targetSum, return the number of paths where the sum of the values along the path equals targetSum. The path does not need to start or end at the root or a leaf, but it must go downwards (i.e., traveling only from parent nodes to child nodes).

https://leetcode.com/problems/path-sum-iii/

Explanation:

we can use the pre-order tree traversal to calculate the path sum for each tree node. In a pre-order traversal, we first visit the root node. Then, we visit the left and right subtrees. Therefore, we can guarantee a downward path between any two nodes in a pre-order traversal sequence. For example, the pre-order path sum sequence of the example binary tree is:

        Maintein a pre sum array while DFS
                     10[10]
                    /   \
            [15,5] 5      -3[7, -3]
                  / \        \
        [18,8,3] 3   2[17,7,2] 11 [18, 8, 11]
                / \   \
    [21,11,6,3]3  -2   1 [18,8,3,1]

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        def pathSumUtil(root, target_sum, prefix_sum):
            if not root:
                return
            
            prefix_sum = prefix_sum + [0]            
            for i in range(0, len(prefix_sum)):
                prefix_sum[i] += root.val
                if prefix_sum[i] == target_sum:
                    self.res += 1
            
            pathSumUtil(root.left, target_sum, prefix_sum)
            pathSumUtil(root.right, target_sum, prefix_sum)
            
        self.res = 0
        pathSumUtil(root, targetSum, [])
        
        return self.res

There is a catch in the above code:

Instead of

👉 Case1: prefix_sum = prefix_sum + [0] if we use

👉 Case2: prefix_sum += [0] , The code will not work.

If we use the later one , then it will modify the existing list , while the former one creates a new list.

So For the given example , the output is as follows: