Leetcode Problem 124. Binary Tree Maximum Path Sum
Leetcode Solutions
Post Order DFS for Maximum Path Sum in Binary Tree
- Initialize a global variable
max_sumto negative infinity. - Define a recursive function
max_gain(node)that:- Returns 0 if
nodeis 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_sumwith the maximum ofmax_sumand 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.
- Returns 0 if
- Call
max_gain(root)to start the recursion. - Return the value of
max_sum.
Ask Question
Programming Language
Purpose:
image/screenshot of info(optional)
Full Screen
Loading...
Suggested Answer
Answer
Full Screen
Copy Answer Code
Loading...