Binary Tree Maximum Path Sum - DFS - Leetcode 124 - Python

0:00 - Read the problem
4:26 - Drawing Explanation
11:56 - Coding Explanation

leetcode 124

#dfs #python

Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[bowenli]

When I search for an explanation, yours would always be my first choice, even though I don't use python, the way you explain each problem is just informative and enlightening, thank you!

[katzy]

I've noticed you tend to do that list by reference trick for primitive values. Python also has built in way to do that, you can declare the variable normally, and then inside the DFS, do "nonlocal" res.

def max_path_sum(root):
res = root.val
def dfs(node):
nonlocal res
if not node:
return 0

[supercarpro]

Mate if it wasn't for your vids I'd be so lost. Was able to do this hard problem on my own today after studying your vids for months. I haven't tried it since 4 months ago but was easily able to come to the solution after learning your patterns. This was just a postorder traversal. Thanks

[moto.kartik]

This is the best explanation for this problem I've ever seen. I struggled so much with wrapping my head around the solution in CTCI. Yours makes so much more sense, I wasn't even all the way through your explanation, but was still able to use what I learnt from it to code this up quickly on Leetcode. Thank you man, you're a legend!

[Nick-kbjc]

Thank you so much for this explanation. I don't know who comes up with these Leetcode problems but this problem was so damn confusing. Leetcode doesn't provide enough example inputs/outputs for Hard problems like this. I had no idea what was defined as a "path" and it was so frustrating because I was running the solution code and still not understanding why I was getting certain values.

[siqb]

Thank you so much for this brilliant explanation. One tiny remark: Perhaps using a "nonlocal res" in the dfs() function and saving the direct sum instead of a list might have been more clean.

[minh]

can't believe that actually solved that many problem and upload the explanation to Youtube :D . Currently, start my leetcode prac and found your channel here. Amazing work.

[mohamedhabibjaouadi]

Thank you for the wonderful content.
My question is why going with the array syntax for res, it would be simpler syntactically to use a normal variable.
The Javascript equivalent, note that functions mutate global variables (wouldn't recommend it but it works):
let res = 0
const dfs = (root) => {
if (!root){
return 0
}

let leftMax = dfs(root.left)
let rightMax = dfs(root.right)

leftMax = Math.max(0, leftMax)
rightMax = Math.max(0, rightMax)

res = Math.max(res, root.val + leftMax + rightMax)

return root.val + Math.max(leftMax, rightMax)
}

const maxPathSum = (root) => {
res = root.val
dfs(root)
return res
};

[srinadhp]

Spent so much time on this problem to understand the problem statement.. yours is by far the best explanation on what is expected of the problem and how to solve it as well.
The idea of splits and why we should send 0 is very helpful to understand.
Lots of appreciations! Keep up the good work! You are helping a lot!!

[linli]

I am totally stunned by this solution. You are so amazing.

[gaaligadu]

Highly underrated channel! Much Appreciated Content !

[Grawlix]

BTW, you can directly plug in '0' as an option when returning from the recursive function. In that case, you only need two or three 'max()' operations, not four:

class Solution:
def maxPathSum(self, root: Optional[TreeNode]) -> int:
self.res = root.val
def dfs(node):
if not node:
return 0
right = dfs(node.right)
left = dfs(node.left)

self.res = max(self.res, node.val + left + right)
return max(node.val + max(left, right), 0)
# Alternate return statement:
# return max(node.val+left, node.val+right, 0)

dfs(root)
return self.res

[numberonep]

a version without the global variable res (it worked for me at least):
class Solution:
def maxPathSum(self, root: Optional[TreeNode]) -> int:
def dfs(root):
if not root:
return 0, float("-inf")
left, wl = dfs(root.left)
left = max(left, 0)

right, wr = dfs(root.right)
right = max(right, 0)

res = max(wl, wr, root.val+left+right)
return root.val+max(left, right), res

return dfs(root)[1]

[yu-jencheng]

Your explanation is so brilliant and clear so that it seems like this is a medium or even easy problem instead of hard!
Really appreciate your work and I really think Leetcode should use your solutions whenever possible!

[themagickalmagickman]

I actually solved this one on my one, granted its one of the easier hard problems (and my code ran pretty slow, beat 28%). However, I originally misinterpreted the question as find the max subtree, not path. Luckily it was literally one line of code difference between the two problems the way I solved it, but its a good reminder to make sure you really understand what is being asked.

[cavinkumaranmahalingam]

Hi, my concern is "How am i supposed to come with such logics when I'm given such problems in any interview?". If you got anything other than "Through practice !", then I would love to know ; )

[AnkitaNallana]

So in the end, it came down to split at that node or no-split and continue down a path (determined by max(leftMax, rightMax)) -- Took me a while but yes, it's so much easier to understand after

[yunierperez]

Excellent explanation thanks! Just curios why 'res' needs to be an array if you are only using the 0 index, is this a python thing?

[Rob-]

This one really confused me. Thanks so much for your explanation.

[monicawang]

heyy quick confirmation question: I notice that the dfs function has return statement after we update res[0], but this very last value that's returned didn't get used, does it mean it's for the root to pass to its parent? (but since it's already the root, it won't pass it further, so we just ignore it?
Thank uu!! really love ur videos!!