Python solution with comments.


  • 1
    C
    # Recursively 
    def maxPathSum(self, root):
        self.res = -sys.maxsize-1
        self.oneSideSum(root)
        return self.res
        
    # compute one side maximal sum, 
    # (root+left children, or root+right children),
    # root is the included top-most node 
    def oneSideSum(self, root):
        if not root:
            return 0
        l = max(0, self.oneSideSum(root.left))
        r = max(0, self.oneSideSum(root.right))
        self.res = max(self.res, l+r+root.val)
        return max(l, r)+root.val

  • 3
    C

    A little bit improvement, if the root is None we can output 0 instead of MinInt, and then we can set self.res to node.val .

    def maxPathSum(self, root):
        if not root:
            return 0
        self.res = root.val
        self.oneSum(root)
        return self.res
        
    def oneSum(self, node):
        if not node:
            return 0
        l = max(0, self.oneSum(node.left))
        r = max(0, self.oneSum(node.right))
        self.res = max(self.res, node.val+l+r)
        return node.val + max(l, r)

Log in to reply
 

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