437.-path-sum-iii.md

437. Path Sum III

• Medium

• 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).

Analysis

Let's go over the example and see what happens.

Now if we consider the nodes from the bottom to the top (from leaf to root). For node 3, the possible sums come from [3, -2]. Then by adding 3 to them we have [6(3+3), 1(-2+3),3(0+3)]. Here since the path doesn't have to be connected all the way to the leaves, we have the choice to abandon the leaves, therefore there is a (0+3) in the list of possible sums.

Now if we consider node 2, the possible sums come from [-1]. So the choices we have are [1, 2].

So here we have found a pattern. For node in the upper level, for example the 5 here. The possible sums come from the combined list in node 3 and node 2. So if we build a list that joins [0] and the results from the left child and the right child, we would have all the sums possible that starts from that point.

Now the core of the problem is fixed, what we need to is to look at the judging part. Since the path doesn't have to go through roots or the leaves, we have to check if we have met the target in each level. Since there are negative values in the tree, we would not be abandoning any possibility in case by adding a negative value it comes back to the target.

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        self.number=0;
        if root:
            self.helper(root, targetSum)
        return self.number
        
        
    def helper(self, root, targetSum):
        possible=[0]
        if root.left:
            possible+=self.helper(root.left,targetSum)
        if root.right:
            possible+=self.helper(root.right,targetSum)            
            
        for i in range(len(possible)):
            possible[i]+=root.val
            if possible[i]==targetSum:
                self.number+=1
        
        return possible;