```
def maxPathSum(self, root):
"""
:type root: TreeNode
:rtype: int
"""
self.maxsum = float("-inf")
def dfs(root): # get largest path from children to root
if not root:
return 0
leftToRoot = max(0, dfs(root.left))
rightToRoot = max(0, dfs(root.right))
self.maxsum = max(self.maxsum, leftToRoot+root.val+rightToRoot)
return max(leftToRoot, rightToRoot) + root.val
dfs(root)
return self.maxsum
```