12 lines of Python code, fast and easy to understand

  • 8
    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

  • 0

    Very easy to understand! Thanks.

    Hint: The integer is not necessarily positive.

  • 2

    @xuzheng1111 the given solution deals with negative numbers just fine. the l and s variables are used to track "one-side" 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 and rs track the max path (that doesn't go through the root), so they are initialized with None to represent the minimum value possible (max will consider None to be the lowest value possible).

  • 4

    Just a note, but it would be even easier to understand with clear variable names, particularly for newbies.

    A clear name for dfs, l, r, ls and rs, in particular, would make this a wonderful example for all.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.