124. Binary Tree maximum Path Sum Leetcode Solution
Binary Tree maximum Path Sum Leetcode Problem :
A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.
The path sum of a path is the sum of the node’s values in the path.
Given the root of a binary tree, return the maximum path sum of any non-empty path.
Binary Tree maximum Path Sum Leetcode Solution :
Constraints :
- The number of nodes in the tree is in the range [1, 3 * 104].
- -1000 <= Node.val <= 1000
Example 1:
- Input: root = [-10,9,20,null,null,15,7]
- Output: 42
Intuition :
Considering possible paths, We have to select a single path from a subtree root the left, and one to the right, and take the maximum possible answer considering all possible sums between them.
Approach :
- Recursively explore the tree and get leftSum and rightSum.
- At each return point, you have to either return the sum upto the current node from either of the subtrees, since we have to take a single path to which we can add, or just the node itself in case the sub-path is negative.
- The answer could either be the current node, or one of the following three paths:
- Curent node + leftAns
- Current node + rightAns
- leftAns + currentNNode+ rightAns
- The answer could either be the current node, or one of the following three paths:
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Code :
class Solution {
public:
int findMaxPathSum(TreeNode* node, int & maxi) {
if (node== NULL) return 0;
int left= max(0, findMaxPathSum(node-> left, maxi));
int right = max(0, findMaxPathSum(node-> right, maxi));
maxi = max(maxi, (left + right) +node->val);
return max(left, right) +node->val;
}
int maxPathSum(TreeNode* root) {
int maxi = INT_MIN;
findMaxPathSum(root, maxi);
return maxi;
}
};
public class Solution {
public int maxPathSum(TreeNode root) {
int[] maxi = {Integer.MIN_VALUE}; // Using an array to store the max value
findMaxPathSum(root, maxi);
return maxi[0];
}
private int findMaxPathSum(TreeNode node, int[] maxi) {
if (node == null) return 0;
int left = Math.max(0, findMaxPathSum(node.left, maxi));
int right = Math.max(0, findMaxPathSum(node.right, maxi));
maxi[0] = Math.max(maxi[0], left + right + node.val);
return Math.max(left, right) + node.val;
}
}
class Solution:
def maxPathSum(self, root: TreeNode) -> int:
def findMaxPathSum(node):
nonlocal maxi
if not node:
return 0
left = max(findMaxPathSum(node.left), 0)
right = max(findMaxPathSum(node.right), 0)
maxi = max(maxi, left + right + node.val)
return max(left, right) + node.val
maxi = float('-inf')
findMaxPathSum(root)
return maxi
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment