Path Sum III | Day 8 | Prefix Sum [ August LeetCoding Challenge ] [ Leetcode - 437 ] [ 2020 ]

The day 8 problem in August Leetcoding Challenge. ( Path Sum III ).

Check out our other popular playlists:

0:00 Path Sum III Problem Statement
1:00 Brute Force Approach
3:34 Prefix Sum

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

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

Example:

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

10
/ \
5 -3
/ \ \
3 2 11
/ \ \
3 -2 1

Return 3. The paths that sum to 8 are:

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

If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful.

#coding #interview #programminglife #programmingisfun #programmer #tech #software #codinglife #leetcode

[AlgorithmsMadeEasy]

We hope you all are enjoying the August leetcoding challenge!!! Don't forget to leave a comment!!! Please like the video to support us!!!
Questions you might like:
Struggling in a question??
Leave in a comment and we will make a video!!!🙂🙂🙂

[AdityaDey]

What is the purpose of using Map or can we use set instead of map?

[akhildeshneni]

please use a good quality recorder and mic

[sagargiri]

what is the time space complexity for both the solutions ?

[vijayakumareyunni]

Most of the videos for this problem seem like code walkthru without explaining "why" an approach has to be followed.

[sangamkumar]

Need a loudspeaker to hear you. But nice solution.

[VipinKumar-lvbk]

why are you taking everything as static ?
Here is a soln without any static member:-
class Solution {
public void preorder(TreeNode root, int currSum, HashMap<Integer, Integer> map, int targetSum, int[] count){
if(root == null)
return;
currSum += root.val;
if(currSum == targetSum)
count[0]++;
count[0] += map.getOrDefault(currSum - targetSum, 0);
map.put(currSum, map.getOrDefault(currSum, 0)+1);

preorder(root.left, currSum, map, targetSum, count);
preorder(root.right, currSum, map, targetSum, count);

map.put(currSum, map.get(currSum)-1);
}
public int pathSum(TreeNode root, int targetSum) {
int[] count = new int[1];
HashMap<Integer, Integer> map = new HashMap<>();
preorder(root, 0, map, targetSum, count);
return count[0];
}
}

[davegeraghty]

your mic is so low, i have my headphones and soundcard at full volume to hear you

[ss]

sound is too low and explanation is too high(very superb

[fatahmo]

I cannot hear you, please use proper Mic.