# Very short and easy Java solution

• Bottom-up approach. Build up max path from leaf to root. At each node `cur`, we check `left + cur` (left path + current root), `right + cur` (right path + current root), and `left + cur + right` (left path + current root + right path). Then we return `max(left + cur, right + cur)`, because ancestors can only use one of the left or right paths.

Later on I found checking `left + cur`, `right + cur`, `left + cur + right` unnecessary, because we don't actually want to return negative values to ancestors (it's like another Leetcode question: `53. Maximum Subarray`). Then it's guaranteed that `left >= 0 && right >= 0`, and the max path sum at current root is simply: `left + cur + right`.

Corner case: max path sum is a negative value (root is negative). Need to set result = root.val initially.

Initial version (4ms):

``````public class Solution {
private int result;

public int maxPathSum(TreeNode root) {
result = root.val;
getMaxPathSum(root);
return result;
}

private int getMaxPathSum(TreeNode root) {
if (root == null) {
return 0;
}
int left = getMaxPathSum(root.left);
int right = getMaxPathSum(root.right);
// check the path sum at current node (actually unnecessary, see concise version below)
int sum = Math.max(left+right, Math.max(left, right)) + root.val;
result = Math.max(result, sum);
return Math.max(0, Math.max(left, right) + root.val);
}
}
``````

A more concise and faster version (2ms):

``````public class Solution {
private int result;

public int maxPathSum(TreeNode root) {
result = root.val;
getMaxPathSum(root);
return result;
}

private int getMaxPathSum(TreeNode root) {
if (root == null) {
return 0;
}
int left = getMaxPathSum(root.left);
int right = getMaxPathSum(root.right);
// since we always return non-negative values, simply use (left + right + root.val) to get the max path sum
result = Math.max(result, left + right + root.val);
return Math.max(0, Math.max(left, right) + root.val);
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.