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) return 0
@xuzheng1111 the given solution deals with negative numbers just fine. the
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).
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).
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.