# Binary Tree Maximum Path Sum

• where does my solution go wrong?
I think the maximum path sum is max of three source:
left tree maximum path sum
right tree maximum path sum
the maximum path that passes root
'''

public int maxPathSum(TreeNode root) {
// write your code here
if (root == null) return Integer.MIN_VALUE;
int leftPathSum = maxPathSum(root.left);
int rightPathSum = maxPathSum(root.right);
int maxSumPassRoot = root.val + helper(maxPathSumFromRoot(root.left), maxPathSumFromRoot(root.right));

``````    return Math.max(Math.max(leftPathSum, rightPathSum), maxSumPassRoot);
}

private int maxPathSumFromRoot(TreeNode node) {
if (node == null) return Integer.MIN_VALUE;
int leftSum = maxPathSumFromRoot(node.left);
int rightSum = maxPathSumFromRoot(node.right);

if (leftSum < 0 && rightSum < 0) return node.val;
return node.val + leftSum >= rightSum ? leftSum : rightSum;

}

private int helper(int a, int b) {
int ret = 0 + (a >= 0 ? a : 0) + (b >= 0 ? b : 0);
return ret;
}
``````

'''

• @kevincoding The value of the node maybe negative. So the maximum path sum can be just the root.

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