```
In this simple solution, post-order traversal is done.
Once a node is visited, sum = maxLeft + root.val + maxRight; and it is compared with global maxPath.
Value returned at each node is max(0, maxLeft + root.val, root.val + maxRight).
To maximize the maxPath, parent can visit either left or right sub-tree of its child if one of them is greater than 0.
int maxPath = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
maxPathHelper(root);
return maxPath;
}
int maxPathHelper(TreeNode root) {
if(root == null)
return 0;
int maxLeft = maxPathHelper(root.left);
int maxRight = maxPathHelper(root.right);
int sum = maxLeft + root.val + maxRight;
if(sum > maxPath)
maxPath = sum;
return Math.max(0, Math.max(maxLeft + root.val, root.val + maxRight));
}
```