🚀

End of Year Sale: Use Coupon Code END2025 to Get Extra 25% Off.

00DAYS
:
15HOURS
:
59MINUTES
:
25SECONDS

Leetcode Problem 124. Binary Tree Maximum Path Sum

124. Binary Tree Maximum Path Sum

Leetcode Solutions

Post Order DFS for Maximum Path Sum in Binary Tree

  1. Initialize a global variable max_sum to negative infinity.
  2. Define a recursive function max_gain(node) that:
    • Returns 0 if node is null (base case).
    • Recursively calls itself for the left and right children of node.
    • Calculates the gain from the left and right subtrees, ignoring negative gains.
    • Updates max_sum with the maximum of max_sum and the sum of the node's value and gains from both subtrees.
    • Returns the node's value plus the maximum gain from either the left or right subtree.
  3. Call max_gain(root) to start the recursion.
  4. Return the value of max_sum.
UML Thumbnail

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...