Binary Tree Maximum Path Sum - DFS - Leetcode 124 - Python
Вставка
- Опубліковано 25 чер 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
Twitter: / neetcode1
Discord: / discord
⭐ BLIND-75 SPREADSHEET: docs.google.com/spreadsheets/...
💡 CODING SOLUTIONS: • Coding Interview Solut...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
🌲 TREE PLAYLIST: • Invert Binary Tree - D...
💡 GRAPH PLAYLIST: • Course Schedule - Grap...
💡 BACKTRACKING PLAYLIST: • Word Search - Backtrac...
💡 LINKED LIST PLAYLIST: • Reverse Linked List - ...
Problem Link: neetcode.io/problems/binary-t...
0:00 - Read the problem
4:26 - Drawing Explanation
11:56 - Coding Explanation
leetcode 124
This question was identified as a facebook interview question from here: github.com/xizhengszhang/Leet...
#dfs #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission. - Наука та технологія
🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤
Q: we only need to get the max sum WITH split, and we already update it inside of the dfs, then why we still need to return the max sum WITHOUT split from the dfs?
i wonder how this works with negative values, shouldnt "leftMax = max(leftMax, 0)" turn any negative number into 0 ?
@@AnnieBox how do you think we update leftMax and rightMax then?
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!
+1. I use Java, but i watch your videos for logical solution and then implement in java on my own (or watch other Java solution videos to refer the implementation details)
Yes, same! I use C++ but always come for explanation here :)
@@hitarthdaxeshbhaikothari1688 same here bro .
+1 this is a very good channel.
I find it a great way to understand it by translating his Python code to the language I use
Very well explained! I love your videos so much. Your channel is my first resort when I am stuck with complex algorithms. Even the Leetcode solutions are not this simple to understand. Thank you so so much! :)
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!
Here's using nonlocal and also not having to check leftMax and rightMax twice for 0
class Solution:
def maxPathSum(self, root: Optional[TreeNode]) -> int:
res = root.val
def traverse(node):
if not node:
return 0
leftMax = traverse(node.left)
rightMax = traverse(node.right)
nonlocal res
res = max(res, node.val + leftMax + rightMax)
return max(0, node.val + max(leftMax, rightMax))
traverse(root)
return res
For some reason, I find it more intuitive to only use max() for selecting the largest choice, rather than also using it to coerce negatives to zero:
def maxPathSum(self, root: Optional[TreeNode]) -> int:
def maxLeg(root: Optional[TreeNode]) -> int:
nonlocal max_path
if not root:
return 0
l = maxLeg(root.left)
r = maxLeg(root.right)
p = root.val
max_leg = max(p, p + l, p + r)
max_path = max(max_path, max_leg, p + l + r)
return max_leg
max_path = -1001
maxLeg(root)
return max_path
can't believe that actually solved that many problem and upload the explanation to UA-cam :D . Currently, start my leetcode prac and found your channel here. Amazing work.
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]
did u handle the case where root.val > root.val + max(left, right) ?
gj man. The code is indeed concise and beautiful
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
etc.....
Nice explanation . Very helpful . The way of explaining through diagram makes the things crystal clear .
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!!
Dude, same here. I hated this problem.
I am totally stunned by this solution. You are so amazing.
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
BRILLIANT explanation, thank you Neetcode!
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!
Awesome explaination of the problem with the optimised solution approach 🔥🔥
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
def dfs(node):
if not node:
return 0, float("-inf")
left, left_max = dfs(node.left)
right, right_max = dfs(node.right)
return max(node.val, node.val + max(left, right)), \
max(node.val, node.val + max(left, right, left + right), left_max, right_max)
_, max_val = dfs(root)
return max_val
Great explanation! may talk about time complexity too.
Wow! You're the master! Thanks for sharing!
Lovely content btw, i can't believe how simple u make it
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.
Exactly. I coded a solution assuming 1 node is not 'non-empty', since there is no 'path'... Problem description is very unclear.
requesting more interview problems, thank you as always
Highly underrated channel! Much Appreciated Content !
Glad it's helpful!
In case this helps things 'click' for anyone, I realized this is really similar to Maximum Subarray. In fact if the tree had no splits (were just a linked list) it would be the same algo. But since the tree _can_ split, it just means we have _two_ running sums to look at instead of one.
yeah there is no way i'm solving this in 45 minutes interview question ...
All leetcode problems should be like this
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.
how to do that?
How to do that? I can’t use a single variable for res because it always gives an error
@@dongdongchen455 in the dfs function at the top just define 'nonlocal res' at the top
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
};
Try to run exact code in Python. You get error because you gonna change that "res" is not defined in that sub function I guess or you cannot mutate global primitive value
Keep sharing new videos ! Your videos are awesome :)
This one really confused me. Thanks so much for your explanation.
explained so smoothly!!!👌👌👌
Another way to conceptualise what constitutes a path is to only have those nodes or vertices in consideration that have at most 2 edges.
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.
Best explanation. Downgraded the question to Medium level. Thank you!
nice and neat explanation!! 👍
Another banger of a solution. I was so close, yet so far :')
Awesome explanation. I solved but took some times and mistakes but what I learned is that if you don't solve problem on paper, don't code it. You are likely to go towards a dead end in 45 minute interview. Better solve it fully on the paper with all edge cases and then coding is like 5 minutes
Thanks for making such great content for learning,
I have one question "how much time you require to solve hard question like this ?"
very clear! thank you!
Do you have a github link with your code solutions? Your explanations are amazing!
Such a clean and clear explanation!
such an amazing video.
You are just great!
I'm a little confused as to how the result gets updated to include conditions where you don't split. ie, we never really check for cases where we only take a path 1 way if that maxes sense
The question says , the path does not need to pass through the root
Great explanation! Thank you so much.
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!!
Yup thats exactly correct! and thanks for the kind words
@@NeetCode Heyy NeetCode, I was doing this problem again and noticed that you used 'res' as an array whereas I just used it as a variable. However, when everything else stays the same, it gives scope error and I had to add "nonlocal res" in the dfs function. I'm confused that both methods are changing 'res' in the inner function, but why does your method not need "nonlocal"?
@@monicawang8447 You can modify lists, sets, dictionaries that are initiated outside of the function but you can't do that with strings/ints (which sounds like what you did at the end). Because you set res as an integer instead of a list, you have to add the words nonlocal for python to know that it has to modify the variable outside of the dfs function. Just a python quirk, hope that helps
Returning the value of the actual root would assume that the path traverses through root, so it could be solution to a problem which has that constraint I believe (for anyone reading this later)
U a God. I thought I had to implement dp somewhere, but glad I didn't! Thanks!
Python implementation:
class Solution(object):
def maxPathSum(self, root):
"""
:type root: TreeNode
:rtype: int
"""
self.ans = float('-inf')
def dfs(root):
if not root:
return 0
left = dfs(root.left)
right = dfs(root.right)
left = max(left, 0)
right = max(right, 0)
self.ans = max(self.ans, root.val + left + right)
return root.val + max(left, right)
dfs(root)
return self.ans
In other languages you can use static variable inside the function instead of global variable
or an instance variable, anything works
either way its not actually global just outsidd the scope of the inner method
Amazing explanation ❤
Thank you very much!
Shouldn't we return max (dfs(root), res[0]) as the result (it could be the case that either left or right path is negative)?
The question says , the path does not need to pass through the root.
This is gold.
good solution thank you
thx!! But I have a question. Why we use the array to store the final result?
@Caleb Rigg explains this well below
How can be space complexity be O(h) we aren't using any extra memory ,are we?
Good question, the memory comes from the recursion call stack.
@@NeetCode thank you 😁
general question, when analyzing trees, often you are calculating something recursively, is that considered overlapping subproblems or not? and are binary trees considered inherently optimal substructures? or not. thanks! btw love your videos and subbed!
Hey, not sure if you still need the answer but here goes... Generally with a tree all nodes are unique so there are no sub-problems like in fibonacci series etc. In the latter case, we have non-unique nodes such as 2, 3, 5 which we have to traverse again to get to the bigger solution
I was expecting an implementation kinda similar to the house robber III prob lem
What is all the values are negatives?
Great solution and video! Why does using a list for the res make modifying it within the recursive function easier?
It's not really "easier" but it avoids having to specify "nonlocal" inside the dfs function. IMHO using a list for res is not as intuitive, but you save a whopping 1 line of code.
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?
In python, you can read a variable from a higher scope (meaning from outside the function) without a problem. But if you try to modify that variable, it'll think you are trying to create a new local variable, leading to exceptions/bugs. To modify the preexisting variable from outside the function, you need to use the nonlocal keyword.
For some reason, neetcode guy decided to avoid nonlocal in favor of a hack. He uses a list for his higher-scoped variable because then he can store the actual value inside of it and modify that rather than the list itself, avoiding the issues I mentioned above. But don't do this. Use nonlocal.
In addition to nonlocal, there is a global keyward that does the same but for globals. Neetcode refers to res as a global variable, but it's not. It belongs to the outer function.
I just paused the video to write a comment here to say that I feel like I've watched so much of your content, at this point it just feels like I'm talking to you lol.
koi company nikaali wikaali?
Could you give the time complexity and space complexity ?
Thanks man
Amazed.
Here is the cpp version with code explanation:
int res = INT_MIN;
int maxPathSum(TreeNode* root) {
dfs(root);
return res;
}
// return max value through current node
// max value either comes from:
// 1. split at current node;
// 2. split through parent node, max value current node could provide.
int dfs(TreeNode *node) {
if (!node) {
return 0;
}
int left = dfs(node->left);
left = max(left, 0);
int right = dfs(node->right);
right = max(right, 0);
// split at current node.
res = max(res, node->val + left + right);
// not split to parent level, max value current node could provide
return node->val + max(left, right);
}
thank you! Hope this one like and a comment support the channel!
Great video, is there a github location where I can find all your codes?
yes.. navigate to this url
github.com/neetcode-gh/leetcode
Ok let's write some more neetcode if you says so
I am still confused about line 24. Can anyone explain to me how it works?
3:17 "this(implying 2+1+3+5) is obviously the maximum we can create"
BUT NO the right sub tree 4+3+5 =12 is the max sum path.
I don't understand, why do you need to make res into a list?
What's the best way to solve without using the global variable?
Return tuple of values (max_path_without_splitting, max_path_with_splitting)
What is the time complexity ?
thanks
you can just use `self.res` instead of [res] to modify the value globally. using the properties of a list to achieve this might be seen as a little hacky by the interviewer.
so why does the list for res allow it to be changed in the function?
@Nolan were you able to figure it out?
@@minyoungan9515 In Python, lists are a mutable object, while primitive type assignments are not (You can think about this like saying lists are always passed by reference, and objects like integers are not). So by passing a list containing a value, the reference to the list isn't lost, yet we're able to change the value inside of it. Another work-around would be to declare the result within the object, where it can be referenced using self.res . Another choice would be to define res outside of the dfs() function, and then define it again within the function using the nonlocal keyword.
@@avenged7ex Thanks for the explanation :) That makes sense
why do we need computations for path sum with split then? someone please enlighten me on this 😮💨
can anyone tell me time and space complexicity please?
this is kinda like house robber 3
God's work
Can anyone provide O(n^2) solution to this problem ?
Can someone explain the concept of adding 0 while updating leftMax and rightMax?
The idea behind comparing with 0 is - We don't want to add up negative numbers in the path. Because that would decrease the sum. So we compare with 0. If leftMax is negative, max(leftMax, 0) with give 0. Adding 0 to the result will not effect the result.
can you guys explain why the res is list instead of a simple variable
simple variables are immutable (think of this as passed by value), whereas, lists are mutable (passed by reference). In order to change the value of the result, he's wrapped it in a list so that the reference to the answer is never lost, while allowing him to alter the value within the lists contents. Another work around would be to declare the res variable as an instance of the Solution class (self.res). Or by declaring it outside the dfs() function, and also within it using the keyword nonlocal (i.e. nonlocal res).
@@avenged7ex interesting so was the list used to improve performance?
@@Ifeelphat no, it was used to increase readability
it shows UnboundLocalError when a simple variable is used instead of a list. that's what it did for me.
@@avenged7ex tuples are immutable too but it works with them.
This problem should be marked "Easy with Leetcode video" lol. Thank you for making things so comprehensive !
I first tried to solve the question without considering the single path and later I realized it is not allowed
Can anyone explain why he used res[0], why not just use res, not make it a list since the start declaration ?
global variable declaration i think. ChatGPT suggested this.
leftMax is a node, how come `max(leftMax,0)` returns a value?
LeftMax isn't a node, it is the returned value from the dfs() call which is passed the node as a parameter. The code runs recursively until the node is determined to be null (meaning we've reached the end of the tree) and return 0. At the bottom of the recursion stack we calculate the max values between this new 0 value and the value of the leaf node, and return a maximum value (see how we just returned the max? this is the integer value leftNode is assigned). Now the recursion calls begin to finish, all-the-while passing the previous maximums to the leftMax and rightMax variables.
u have a gift my guy
why he have used a list for the res , why not just a integer? can anyone make me understand please!
Using a list for the res allows us to update the result within the helper function. If res was instead simply a variable that stores an integer, when we try to update it within the helper function, it will create a new variable called res local to the helper function. We use a list to get around this problem or you could alternatively use a variable with the nonlocal keyword
@@angelinazhou667 yes
Or can use a class variable using self
Why is your `res = [root.val]` as opposed to `res = root.val`? Why make it a list?
why make the global variable - res - an array with one item? why not just set the value to the item itself? we never push or append anything else to it. just curious, thank you for all that you've done.
it works even if its not used as array, actually it should be just a simple variable
What if all the nodes are negative?
This is handled by always including the current node's value in the max() calls. The result variable would be assigned to the largest individual node value in that case, as it is always included in any max() call.
This problem was something
could someone explain how to do this without the global variable
I did it using a pair of in c++. code is below
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
private:
pair dfs(TreeNode* root) {
if (!root)
return make_pair(0,INT_MIN);
pair left = dfs(root->left);
pair right = dfs(root->right);
int currPath = root->val + max(max(left.first,0), max(right.first,0));
int currMaxPath = root->val + max(left.first,0) + max(right.first,0);
int maxPath = max(max(left.second,right.second), currMaxPath);
return make_pair(currPath, maxPath);
}
public:
int maxPathSum(TreeNode* root) {
pair result = dfs(root);
return result.second;
}
};
why global would be considered as cheating?
I coded a solution assuming 1 node is not 'non-empty', since there is no 'path'... Problem description is very unclear.
Dude please make videos on path sum 2, 3
The solved the problem but still i wanna see his explanation
the edge cases in leet code suck
I didn't like the explanation. The way it is worded, splitting should never be allowed in a path. So why would you consider a split in updating the path? Of course the algorithm presented here is correct, but the way it is said makes it sound wrong. The way I would describe is - At each node you consider these things - What is the max path that goes through me but stays within my subtree? For that I would need left max and right max and myself added. And the second thing is, what is the max path that goes through me but comes from above? In this case, you pick either left or right max but not both. And when returning, you don't use the path that goes through me and stays within my subtree because the upper nodes can't use that. But you do use it to update global max because it is a valid path.