# 124. Binary Tree Maximum Path Sum (Hard)

https://leetcode.com/problems/binary-tree-maximum-path-sum/

Given a non-empty binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

Example 1:

```Input: [1,2,3]

1
/ \
2   3

Output: 6
```

Example 2:

```Input: [-10,9,20,null,null,15,7]

-10
/ \
9  20
/  \
15   7

Output: 42
```

## Solutions

``````class Solution {
private int max = Integer.MIN_VALUE;

public int maxPathSum(TreeNode root) {
if (root == null) {
return 0;
}

dfs(root);

return max;
}

private int dfs(TreeNode root) {
if (root == null) {
return 0;
}

// Values for left and right can be negative, but the branch with negative outcomes
// will be cut off later
int left = dfs(root.left);
int right = dfs(root.right);

// global maximum, max used to keep the largest one
max = Math.max(max, root.val);
max = Math.max(max, root.val + left);
max = Math.max(max, root.val + right);
max = Math.max(max, root.val + left + right);

// local maximum of adjacent context path
int leftVal = Math.max(root.val, root.val + left);
int rightVal = Math.max(root.val, root.val + right);

return Math.max(leftVal, rightVal);
}
}
``````