class Solution(object):
def maxPathSum(self, root):
def dfs(node): # returns: max one side path sum, max path sum
l = r = 0
ls = rs = None
if node.left:
l, ls = dfs(node.left)
l = max(l, 0)
if node.right:
r, rs = dfs(node.right)
r = max(r, 0)
return node.val + max(l, r), max(node.val + l + r, ls, rs)
if root:
return dfs(root)[1]
return 0
12 lines of Python code, fast and easy to understand


@xuzheng1111 the given solution deals with negative numbers just fine. the
l
ands
variables are used to track "oneside" max sum, and so initialized with zero to indicate that this one side is not being taken into account (hence, it must be zero).lr
andrs
track the max path (that doesn't go through the root), so they are initialized withNone
to represent the minimum value possible (max
will considerNone
to be the lowest value possible).