## 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;
}
``````
Copy The Code &

Input

cmd
root = [1,2,3]

Output

cmd
6

### #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;
}
};
``````
Copy The Code &

Input

cmd
root = [1,2,3]

### #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);
}
}
``````
Copy The Code &

Input

cmd
root = [-10,9,20,null,null,15,7]

Output

cmd
42

### #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)
}
``````
Copy The Code &

Input

cmd
root = [-10,9,20,null,null,15,7]

Output

cmd
42

### #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]
``````
Copy The Code &

Input

cmd
root = [1,2,3]

Output

cmd
6

### #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);
}
}
}
``````
Copy The Code &

Input

cmd
root = [1,2,3]

Output

cmd
6