LeetCode 124. Binary Tree Maximum Path Sum (Algorithm Explained)
ฝัง
- เผยแพร่เมื่อ 11 ก.ย. 2024
- The Best Place To Learn Anything Coding Related - bit.ly/3MFZLIZ
Join my free exclusive community built to empower programmers! - www.skool.com/...
Preparing For Your Coding Interviews? Use These Resources
--------------------
(My Course) Data Structures & Algorithms for Coding Interviews - thedailybyte.d...
AlgoCademy - algocademy.com...
Daily Coding Interview Questions - bit.ly/3xw1Sqz
10% Off Of The Best Web Hosting! - hostinger.com/...
Follow Me on X/Twitter - x.com/nickwhit...
Follow My Instagram - / nickwwhite
Other Social Media
----------------------------------------------
Discord - / discord
Twitch - / nickwhitettv
TikTok - / nickwhitetiktok
LinkedIn - / nicholas-w-white
Show Support
------------------------------------------------------------------------------
Patreon - / nick_white
PayPal - paypal.me/nick....
Become A Member - / @nickwhite
#coding #programming #softwareengineering
![[FULL EP.73] เปิดบ้าน 70 ล้าน "แป้ง Zbing" ยกมาทั้งญี่ปุ่น l เคหสถานบานปลาย l One Playground](http://i.ytimg.com/vi/YBnJhTt07Pg/mqdefault.jpg)
//this is Post Order Traversal, goes from bottom up to the top
//for max_path_sum, we add all positive values of left subtree,right subtree and root and find the maximum
//for the result of method pathSum, we return only the larger sum path from bottom up, either the left or the right, because from a subroot you can only choose one direction to sum
Problem is good, explanation could be better though.
Why don't you explain why you get a max(0, left/right)? You are just repeating after what you are typing. Is this called "algorithm explained"? Same question to the return value.
I think 0 just avoid getting negative number... he didn't explain it.
The reason for max(0, left/right) is because we don't want to decrease our current solution. If the left subtree is less than 0, then it only makes our solution worse, therefore its better to start from beggining (0). The last statement is for choosing better sum from tree. We have to have a path (not sum of paths) so the greater value the better
@@tarsala1995 A single node can form the answer. When all numbers are negative except one, then that non-negative node should be the answer. If all numbers are negative then the biggest of them all should form the answer. This 0 is taking care of those cases. Precisely the next statement where the actual global answer is getting updated.
Although this is a poor explanation for this problem, when he went "boom, boom, boom", my head went "fuq, fuq, fuq".
"its easy what more do I need to explain to you?" does not a good teacher make.
These videos are made after you atleast attempt a question, not to learn a question.
Thats a good problem. Normally we dont traverse like this, i mean updating one local max and one global max at the same time is kind of new for me. Great solution. Opens a new way of looking at tree traversals.
yeah same for me. Brilliant approach
Thanks Nick. I tried this without watching the solution, and kept getting errors because of the possible negative numbers in the nodes. I think the key piece of code is in line numbers 20 and 21.
Since we take a max of 0 and left or right subtree values, we effectively discard any -ve numbers (because they can never make an even bigger path val).
Without these max functions in line 20 and 21, this would work just fine for all BT with nodes as positive values.
In fact the original interview question is to assume that all nodes have positive values and then the interviewer asks you to modify your code if there were negative numbers.
The recursion and all the other calculations can be thought of in 10 mins assuming the candidate has a good grasp at recursion and graph traversals.
Me too! I also kept getting wrong answers for that but still didn't quite understand why does that work when we take max of 0 and right/left sub-tree. What if all the nodes are negative? :(
@@tvishathakur8947 you can draw out a tree and see why taking 0 is better than including a -ve number in your max path sum.. a -ve number can never increase a path sum.
If all numbers are negative, then you need to ask the interviwer what should you return. Those are good clarifying questions actually !
@@psn999100 Yes now I understood! So here in case of negative values it returns the root value. Thankyou! :)
so funny when ur say "fun things going in this recursive function" and second later "I don't even know what I'm saying" LOL
i dont get it, what if the root node is positive values? wouldnt this solution be 9+root+42? and how could this answer be possible if no U turn is allowed for paths?
What if all the Nodes have negative values? You are discarding negative values.
No, the algo would just return the negative value closest to 0.
I think you are confused, man.
I'm glad you pointed out there's no backtracking. The original problem didn't say that, but its obvious from the solution that this is the case.
your other videos are fine, this is one terrible.
Solution is good but you are looking too confused man... I think your explanation made it more complicated
Your clap hurted my ear
the max space Is O(log n) as your recursion (stack) will never exceed log n. Before start for every of next to each other subtrees previous stack will be cleaned
(not true, comments)
Not true, in a binary tree the worst- case height is n not log n. Again, WORST CASE height!!
O(lg n) would be for a balanced binary tree.
I see. You are right guys. Also, I think that is worth mentioning to the interviewer, the balanced and worst cases.
what was the class that he mentioned. The captions read "walkman with alice videos on algorithms"
"you know what I mean" - no we don;t
great video
Great solution! Thanks!
why we need to pass 0 for left and right variables
we compare the with zero because, if we get a negative value from left or right subtree, then we need to just consider the current node in order to maximize the sum. Example : [2 , -1] is your tree, where -1 is the left/right child. If comparison with zero is missing then left = -1, right = 0, curr = 2 , then maxVal = 1, which is wrong. The correct answer is 2. Hence we discard the negative values.
Thank you.
I had problem understand at that return statement
Can anyone help me with why is he returning result and calculating max_path_sum
The max_path_sum indicates the max sum found overall, and the result is sum for the current node, at a certain node how can you decide that whether you should take the left node, or the right node or sum of all three is your answer.
For eg. if the nodes were 15--20--7 then we take the max sum as 15+20+7-->max_path_sum but at this point we don't know this is the max sum for sure, but at this point we know the max sum that can be transferred is 15+20-->max(left,rigth)+current.
love the way he claps!!!
You clearly don’t know how it works.
Man! You look good, talented and to be honest your coding skills are fantastic....
Review
great solution man, although your explanation was horrible (im sorry P) just looking at your solution and dry running it on a random tree did it for me! maintaining two variables/return in a single function is new for me
pls uplod unique path 3 problem on leetcode
He is just writing the code and calling it explanation of the problem.. lol
nick you should also code in C++
please work on your presentation skills, you seem you are not at all interested, just doing it because someone is forcing you to do