Algorithm
Problem Nmae: 124. Binary Tree Maximum Path Sum
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.
Example 1:
Input: root = [1,2,3] Output: 6 Explanation: The optimal path is 2 -> 1 -> 3 with a path sum of 2 + 1 + 3 = 6.
Example 2:
Input: root = [-10,9,20,null,null,15,7] Output: 42 Explanation: The optimal path is 15 -> 20 -> 7 with a path sum of 15 + 20 + 7 = 42.
Constraints:
- The number of nodes in the tree is in the range
[1, 3 * 104]. -1000 <= Node.val <= 1000
Code Examples
#1 Code Example with C Programming
Code -
C Programming
int maxsum(struct TreeNode *node, int *max) {
int l, r, k, s;
if (!node) return 0;
l = maxsum(node->left, max);
r = maxsum(node->right, max);
l = l > 0 ? l : 0; // ignore negative
r = r > 0 ? r : 0;
s = node->val + l + r; // current node + both sides
if (*max < s) *max = s;
k = node->val + (l > r ? l : r); // current node + one side only
return k;
}
int maxPathSum(struct TreeNode* root) {
int max;
if (root) {
max = root->val;
maxsum(root, &max);
} else {
max = 0;
}
return max;
}
Input
Output
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
int maxPathSum(TreeNode* root) {
int maxSum = INT_MIN;
DFS(root, maxSum);
return maxSum;
}
int DFS(TreeNode* root, int& maxSum){
if(!root) return 0;
int left = max(0, DFS(root->left, maxSum));
int right = max(0, DFS(root->right, maxSum));
maxSum = max(maxSum, left + right + root->val);
return max(left, right) + root->val;
}
};
Input
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
int maxVal;
public int maxPathSum(TreeNode root) {
maxVal = Integer.MIN_VALUE;
helper(root);
return maxVal;
}
private int helper(TreeNode root) {
if (root == null) {
return 0;
}
int left = Math.max(helper(root.left), 0);
int right = Math.max(helper(root.right), 0);
int sum = root.val + left + right;
maxVal = Math.max(maxVal, sum);
return root.val + Math.max(left, right);
}
}
Input
Output
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const maxPathSum = function(root) {
let obj = {
max: Number.MIN_SAFE_INTEGER
}
traverse(root, obj)
return obj.max
};
function traverse(node, obj) {
if(node === null) return 0
let left = Math.max(0, traverse(node.left, obj))
let right = Math.max(0, traverse(node.right, obj))
obj.max = Math.max(obj.max, node.val+left+right)
return node.val + Math.max(left, right)
}
Input
Output
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def maxPathSum(self, root):
res = [-float("inf")]
def dfs(node):
if not node: return -float("inf")
l, r = dfs(node.left), dfs(node.right)
mx = max(node.val, l + node.val, r + node.val)
res[0] = max(res[0], mx, node.val + l + r)
return mx
dfs(root)
return res[0]
Input
Output
#6 Code Example with C# Programming
Code -
C# Programming
using System;
namespace LeetCode
{
public class _0124_BinaryTreeMaximumPathSum
{
private int max_sum = int.MinValue;
public int MaxPathSum(TreeNode root)
{
MaxPathSumCore(root);
return max_sum;
}
public int MaxPathSumCore(TreeNode root)
{
if (root == null) return 0;
var leftSum = Math.Max(MaxPathSumCore(root.left), 0);
var rightSum = Math.Max(MaxPathSumCore(root.right), 0);
max_sum = Math.Max(max_sum, root.val + leftSum + rightSum);
return root.val + Math.Max(leftSum, rightSum);
}
}
}
Input
Output