```
private int maxPath = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
traverse(root);
return maxPath;
}
public int traverse(TreeNode root){
if(root == null) return 0;
int left = traverse(root.left) + root.val;
int right = traverse(root.right) + root.val;
int tmpMax = Math.max(left, Math.max(right, root.val));
maxPath = Math.max(maxPath, Math.max(tmpMax, left + right - root.val));
return tmpMax;
}
```