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

Поділитися
Вставка
  • Опубліковано 15 чер 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.
  • Наука та технологія

КОМЕНТАРІ • 158

  • @NeetCode
    @NeetCode  3 роки тому +32

    🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤

    • @AnnieBox
      @AnnieBox 2 роки тому

      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?

    • @kippesolo8941
      @kippesolo8941 10 місяців тому

      i wonder how this works with negative values, shouldnt "leftMax = max(leftMax, 0)" turn any negative number into 0 ?

    • @kippesolo8941
      @kippesolo8941 10 місяців тому

      @@AnnieBox how do you think we update leftMax and rightMax then?

  • @bowenli5886
    @bowenli5886 3 роки тому +193

    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!

    • @shaikdiary
      @shaikdiary 2 роки тому +1

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

    • @hitarthdaxeshbhaikothari1688
      @hitarthdaxeshbhaikothari1688 2 роки тому +3

      Yes, same! I use C++ but always come for explanation here :)

    • @ShivamKumar-qv6em
      @ShivamKumar-qv6em 2 роки тому

      @@hitarthdaxeshbhaikothari1688 same here bro .

    • @mingjuhe1514
      @mingjuhe1514 2 роки тому

      +1 this is a very good channel.

    • @sagivalia5041
      @sagivalia5041 Рік тому

      I find it a great way to understand it by translating his Python code to the language I use

  • @nehascorpion
    @nehascorpion Рік тому +5

    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! :)

  • @KartikeyaPuri45
    @KartikeyaPuri45 4 місяці тому

    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!

  • @minh1391993
    @minh1391993 2 роки тому +3

    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.

  • @katzy687
    @katzy687 11 місяців тому +13

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

  • @ShivamKumar-qv6em
    @ShivamKumar-qv6em 2 роки тому

    Nice explanation . Very helpful . The way of explaining through diagram makes the things crystal clear .

  • @srinadhp
    @srinadhp 2 роки тому

    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!!

    • @Nick-kb2jc
      @Nick-kb2jc 2 роки тому

      Dude, same here. I hated this problem.

  • @supercarpro
    @supercarpro Рік тому +1

    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

  • @numberonep5404
    @numberonep5404 2 роки тому +18

    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]

    • @PhanNghia-fk5rv
      @PhanNghia-fk5rv Місяць тому

      did u handle the case where root.val > root.val + max(left, right) ?

    • @aleksey3231
      @aleksey3231 18 днів тому

      gj man. The code is indeed concise and beautiful

  • @linli7049
    @linli7049 2 роки тому +4

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

  • @yu-jencheng556
    @yu-jencheng556 Рік тому +4

    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!

  • @kartiksoni825
    @kartiksoni825 7 місяців тому

    BRILLIANT explanation, thank you Neetcode!

  • @Nick-kb2jc
    @Nick-kb2jc 2 роки тому +13

    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.

    • @zl7460
      @zl7460 Рік тому

      Exactly. I coded a solution assuming 1 node is not 'non-empty', since there is no 'path'... Problem description is very unclear.

  • @nachiket9857
    @nachiket9857 11 місяців тому +4

    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

  • @JaiSagar7
    @JaiSagar7 Рік тому

    Awesome explaination of the problem with the optimised solution approach 🔥🔥

  • @michaelmarchese5865
    @michaelmarchese5865 2 місяці тому +2

    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

  • @maryamlarijani5550
    @maryamlarijani5550 2 роки тому

    Great explanation! may talk about time complexity too.

  • @chaengsaltz829
    @chaengsaltz829 2 роки тому +1

    Wow! You're the master! Thanks for sharing!

  • @numberonep5404
    @numberonep5404 2 роки тому +1

    Lovely content btw, i can't believe how simple u make it

  • @siqb
    @siqb 3 роки тому +6

    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.

    • @dongdongchen455
      @dongdongchen455 2 роки тому +1

      how to do that?

    • @zhengzuo5118
      @zhengzuo5118 2 роки тому +1

      How to do that? I can’t use a single variable for res because it always gives an error

    • @sagarpotnis1215
      @sagarpotnis1215 Рік тому +1

      @@dongdongchen455 in the dfs function at the top just define 'nonlocal res' at the top

  • @mohamedhabibjaouadi3933
    @mohamedhabibjaouadi3933 Рік тому +6

    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
    };

    • @japarjarkynbyek8494
      @japarjarkynbyek8494 4 місяці тому

      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

  • @rentianxiang92
    @rentianxiang92 2 роки тому

    requesting more interview problems, thank you as always

  • @gaaligadu148
    @gaaligadu148 2 роки тому +2

    Highly underrated channel! Much Appreciated Content !

    • @NeetCode
      @NeetCode  2 роки тому

      Glad it's helpful!

  • @Grawlix99
    @Grawlix99 Рік тому +2

    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

  • @Rob-147
    @Rob-147 11 місяців тому +1

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

  • @mama1990ish
    @mama1990ish 2 роки тому

    Keep sharing new videos ! Your videos are awesome :)

  • @sachinwalunjakar8854
    @sachinwalunjakar8854 Рік тому +1

    Thanks for making such great content for learning,
    I have one question "how much time you require to solve hard question like this ?"

  • @siddhantkhanna9053
    @siddhantkhanna9053 Рік тому

    explained so smoothly!!!👌👌👌

  • @rakeshkashyap84
    @rakeshkashyap84 2 роки тому

    Best explanation. Downgraded the question to Medium level. Thank you!

  • @themagickalmagickman
    @themagickalmagickman 11 місяців тому

    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.

  • @roman_mf
    @roman_mf Рік тому

    Another banger of a solution. I was so close, yet so far :')

  • @hardikjoshi8111
    @hardikjoshi8111 10 місяців тому

    Another way to conceptualise what constitutes a path is to only have those nodes or vertices in consideration that have at most 2 edges.

  • @MySWESpace
    @MySWESpace 2 роки тому +2

    Do you have a github link with your code solutions? Your explanations are amazing!

  • @AnnieBox
    @AnnieBox 2 роки тому

    nice and neat explanation!! 👍

  • @chelsylan8554
    @chelsylan8554 5 місяців тому

    very clear! thank you!

  • @bulioh
    @bulioh 3 місяці тому

    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.

  • @ObtecularPk
    @ObtecularPk 2 роки тому +8

    yeah there is no way i'm solving this in 45 minutes interview question ...

  • @KeyAndLock77
    @KeyAndLock77 5 місяців тому

    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

  • @edwardteach2
    @edwardteach2 2 роки тому

    U a God. I thought I had to implement dp somewhere, but glad I didn't! Thanks!

    • @edwardteach2
      @edwardteach2 2 роки тому

      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

  • @souparnomajumder
    @souparnomajumder 2 місяці тому

    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

  • @yamaan93
    @yamaan93 Рік тому +3

    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

    • @beonthego8725
      @beonthego8725 8 місяців тому

      The question says , the path does not need to pass through the root

  • @monicawang8447
    @monicawang8447 2 роки тому +2

    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!!

    • @NeetCode
      @NeetCode  2 роки тому +1

      Yup thats exactly correct! and thanks for the kind words

    • @monicawang8447
      @monicawang8447 2 роки тому +2

      @@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"?

    • @johns3641
      @johns3641 2 роки тому +21

      @@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

    • @nachiket9857
      @nachiket9857 11 місяців тому

      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)

  • @eamonmahon6622
    @eamonmahon6622 Рік тому

    Great solution and video! Why does using a list for the res make modifying it within the recursive function easier?

    • @howheels
      @howheels Рік тому +1

      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.

  • @anandkrishnan72
    @anandkrishnan72 2 роки тому +1

    such an amazing video.

  • @keremt8727
    @keremt8727 Рік тому +2

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

    • @beonthego8725
      @beonthego8725 8 місяців тому

      The question says , the path does not need to pass through the root.

  • @mitchellhuang5488
    @mitchellhuang5488 2 роки тому +1

    Such a clean and clear explanation!

  • @mingjunma293
    @mingjunma293 2 роки тому +3

    thx!! But I have a question. Why we use the array to store the final result?

  • @albertjtyeh53
    @albertjtyeh53 3 роки тому +2

    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!

    • @tejeshreddy6252
      @tejeshreddy6252 2 роки тому

      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

  • @RS-vu4nn
    @RS-vu4nn 2 роки тому

    In other languages you can use static variable inside the function instead of global variable

    • @colin398
      @colin398 Рік тому

      or an instance variable, anything works
      either way its not actually global just outsidd the scope of the inner method

  • @begula_chan
    @begula_chan 3 місяці тому

    Thank you very much!

  • @yunierperez2680
    @yunierperez2680 3 місяці тому +1

    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?

    • @michaelmarchese5865
      @michaelmarchese5865 2 місяці тому

      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.

  • @mehull408
    @mehull408 6 місяців тому

    Amazing explanation ❤

  • @telnet8674
    @telnet8674 2 роки тому

    I was expecting an implementation kinda similar to the house robber III prob lem

  • @NitinPatelIndia
    @NitinPatelIndia 3 роки тому

    Great explanation! Thank you so much.

  • @mohithadiyal6083
    @mohithadiyal6083 2 роки тому +4

    How can be space complexity be O(h) we aren't using any extra memory ,are we?

    • @NeetCode
      @NeetCode  2 роки тому +11

      Good question, the memory comes from the recursion call stack.

    • @mohithadiyal6083
      @mohithadiyal6083 2 роки тому

      @@NeetCode thank you 😁

  • @hwang1607
    @hwang1607 6 місяців тому

    good solution thank you

  • @onlineservicecom
    @onlineservicecom 2 роки тому

    Could you give the time complexity and space complexity ?

  • @emmatime2016
    @emmatime2016 2 роки тому

    You are just great!

  • @bloodfiredrake7259
    @bloodfiredrake7259 5 місяців тому +2

    What is all the values are negatives?

  • @ilanaizelman3993
    @ilanaizelman3993 2 роки тому +1

    This is gold.

  • @noumaaaan
    @noumaaaan 2 роки тому +1

    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.

    • @farazahmed7
      @farazahmed7 2 роки тому +1

      koi company nikaali wikaali?

  • @ameynaik2743
    @ameynaik2743 3 роки тому

    Great video, is there a github location where I can find all your codes?

    • @TechOnScreen
      @TechOnScreen 2 роки тому

      yes.. navigate to this url
      github.com/neetcode-gh/leetcode

  • @symbol767
    @symbol767 2 роки тому

    Thanks man

  • @Kenspectacle
    @Kenspectacle Місяць тому

    I don't understand, why do you need to make res into a list?

  • @tarek7451
    @tarek7451 2 роки тому +1

    What's the best way to solve without using the global variable?

    • @Saralcfc
      @Saralcfc 2 роки тому

      Return tuple of values (max_path_without_splitting, max_path_with_splitting)

  • @KhoaLe-oc6xl
    @KhoaLe-oc6xl 2 роки тому +4

    This problem should be marked "Easy with Leetcode video" lol. Thank you for making things so comprehensive !

  • @herdata_eo4492
    @herdata_eo4492 2 роки тому

    why do we need computations for path sum with split then? someone please enlighten me on this 😮‍💨

  • @mehershrishtinigam5449
    @mehershrishtinigam5449 Рік тому

    What is the time complexity ?

  • @MrSaurus
    @MrSaurus 8 місяців тому

    I am still confused about line 24. Can anyone explain to me how it works?

  • @NapoleonNol
    @NapoleonNol 2 роки тому

    so why does the list for res allow it to be changed in the function?

    • @minyoungan9515
      @minyoungan9515 2 роки тому

      @Nolan were you able to figure it out?

    • @avenged7ex
      @avenged7ex 2 роки тому +4

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

    • @minyoungan9515
      @minyoungan9515 2 роки тому

      @@avenged7ex Thanks for the explanation :) That makes sense

  • @heisenberg1844
    @heisenberg1844 2 роки тому +1

    Amazed.

  • @anantmittal522
    @anantmittal522 Рік тому

    Can anyone provide O(n^2) solution to this problem ?

  • @tomarintomarin9520
    @tomarintomarin9520 2 роки тому +2

    Ok let's write some more neetcode if you says so

  • @nithingowda1060
    @nithingowda1060 2 роки тому

    can anyone tell me time and space complexicity please?

  • @rishabhverma3615
    @rishabhverma3615 2 роки тому

    Can someone explain the concept of adding 0 while updating leftMax and rightMax?

    • @SandeepKumar16
      @SandeepKumar16 2 роки тому

      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.

  • @justincao7356
    @justincao7356 2 роки тому

    thank you! Hope this one like and a comment support the channel!

  • @darrylbrian
    @darrylbrian 2 роки тому

    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.

    • @VipulDessaiBadGAMERbaD
      @VipulDessaiBadGAMERbaD Рік тому

      it works even if its not used as array, actually it should be just a simple variable

  • @disha4545
    @disha4545 Рік тому

    Can anyone explain why he used res[0], why not just use res, not make it a list since the start declaration ?

    • @shivanshgupta5657
      @shivanshgupta5657 5 днів тому

      global variable declaration i think. ChatGPT suggested this.

  • @satadhi
    @satadhi 2 роки тому

    can you guys explain why the res is list instead of a simple variable

    • @avenged7ex
      @avenged7ex 2 роки тому +6

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

    • @Ifeelphat
      @Ifeelphat 2 роки тому

      @@avenged7ex interesting so was the list used to improve performance?

    • @avenged7ex
      @avenged7ex 2 роки тому

      @@Ifeelphat no, it was used to increase readability

    • @saugatkarki3169
      @saugatkarki3169 Рік тому

      it shows UnboundLocalError when a simple variable is used instead of a list. that's what it did for me.

    • @liamsism
      @liamsism Рік тому

      @@avenged7ex tuples are immutable too but it works with them.

  • @ujjawalpanchal
    @ujjawalpanchal 5 місяців тому +1

    Why is your `res = [root.val]` as opposed to `res = root.val`? Why make it a list?

  • @thevagabond85yt
    @thevagabond85yt Рік тому

    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.

  • @veliea5160
    @veliea5160 2 роки тому

    leftMax is a node, how come `max(leftMax,0)` returns a value?

    • @avenged7ex
      @avenged7ex 2 роки тому

      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.

  • @sankhadip_roy
    @sankhadip_roy 8 місяців тому +1

    why he have used a list for the res , why not just a integer? can anyone make me understand please!

    • @angelinazhou667
      @angelinazhou667 2 дні тому +1

      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

    • @sankhadip_roy
      @sankhadip_roy 2 дні тому

      @@angelinazhou667 yes
      Or can use a class variable using self

  • @akhilattri844
    @akhilattri844 Рік тому

    thanks

  • @ancai5498
    @ancai5498 6 місяців тому

    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);
    }

  • @joshithmurthy6209
    @joshithmurthy6209 2 роки тому

    I first tried to solve the question without considering the single path and later I realized it is not allowed

  • @asrahussain8642
    @asrahussain8642 9 місяців тому

    this is kinda like house robber 3

  • @radishanim
    @radishanim 2 роки тому

    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.

  • @nisusrk
    @nisusrk 2 роки тому

    What if all the nodes are negative?

    • @avenged7ex
      @avenged7ex 2 роки тому

      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.

  • @soukaryasaha3825
    @soukaryasaha3825 Рік тому

    could someone explain how to do this without the global variable

    • @Rob-147
      @Rob-147 11 місяців тому

      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;
      }
      };

  • @gazijarin8866
    @gazijarin8866 2 роки тому

    God's work

  • @mehershrishtinigam5449
    @mehershrishtinigam5449 Рік тому

    u have a gift my guy

  • @anujkhare3815
    @anujkhare3815 Рік тому

    This problem was something

  • @garciamenesesbrayan
    @garciamenesesbrayan 2 місяці тому +1

    why global would be considered as cheating?

  • @zl7460
    @zl7460 Рік тому

    I coded a solution assuming 1 node is not 'non-empty', since there is no 'path'... Problem description is very unclear.

  • @ambujhakhu7531
    @ambujhakhu7531 2 роки тому +1

    Dude please make videos on path sum 2, 3

  • @WeirdAlSuperFan
    @WeirdAlSuperFan Рік тому

    I feel like you're explaining the code line by line but you didn't actually write it in that same order. Would be nice if you explained it in the order you actually wrote it.

  • @tachyon7777
    @tachyon7777 4 місяці тому +2

    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.

  • @kipa_chu
    @kipa_chu 2 роки тому

    This is a confusing solution IMO