[Java] Leetcode 437. Path Sum III [Binary Tree #14]

In this video, I'm going to show you how to solve Leetcode 437. Path Sum III which is related to Binary Tree.

Here’s a quick rundown of what you’re about to learn:

⭐️ Contents ⭐️
⌨️ (0:00) Question Explain
⌨️ (1:40) O(N^2) Approach
⌨️ (6:16) Code
⌨️ (11:32) O(N) Approach
⌨️ (17:56) Code

In the end, you’ll have a really good understanding on how to solve Leetcode 437. Path Sum III and questions that are similar to this Binary Tree.

Now, if you want to get good at Binary Tree, please checkout my Binary Tree playlist.

[jiawen]

For this test case
we can just change the tar's datatype from int to long. Because it just overflow of int.

[maxmelnyk]

Hey Eric! Thanks for the video! If you use global variables, then you gotta take care of nullifying counter at the start of the main call, othervise, its gonna fail by simply calling the function 2 times. Also think about concurrent calls of the function, i would avoid using globals.

[louischou]

why do we need to remove curSum if map.get(curSum) == 1?

[RaviPrakash-rtvx]

Giving wrong output for input

Input:

0<----target sum
// output getting 2, instead of 0 with solution 1

[MeetManga]

Hi this solution could not been passed right now, by a test case
0
a tinny uodate, enjoy!
class Solution {
Map<Long, Integer> map = new HashMap<>();
int count = 0;
public int pathSum(TreeNode root, int targetSum) {
map.put(0L, 1);
dfs(root, targetSum, 0L);
return count;
}
private void dfs(TreeNode root, int targetSum, Long curSum){
if(root == null){
return;
}
curSum += root.val;
count += map.getOrDefault(curSum - targetSum, 0);
map.put(curSum, map.getOrDefault(curSum, 0) + 1);

dfs(root.left, targetSum, curSum);
dfs(root.right, targetSum, curSum);
if(map.get(curSum) <= 1){
map.remove(curSum);
}else{
map.put(curSum, map.get(curSum) - 1);
}
}
}