The maximum path sum can either be in the left subtree or the right subtree so using the postorder traversal is good.

because the maximum will not always go through root, at each node you always check if the sum of the left and right and current node val and store the maximum

at each node, you always return the current node value + the max of left subtree or right subtree
or the node value itself if it's bigger then the left or right subtree.
class Solution(object):
max_val = 10000
def max_path(self,root):
if root:
left = self.max_path(root.left)
right = self.max_path(root.right)
self.max_val = max(self.max_val, max(left,right)+root.val,left+right+root.val,root.val)
#print "at node ", root.val , "left is " , left , "right is " , right, "returning: ", max(max(left,right)+root.val,root.val)
#print "max: ", self.max_val
return max(max(left,right)+root.val,root.val)
else:
return 0
def maxPathSum(self, root):
"""
:type root: TreeNode
:rtype: int
"""
self.max_path(root)
return self.max_val