Easy recursive solution Python(only 8 lines)


  • 0
    G
    def maxPathSum(self, root):
    
        def double(root): # return (max_path_from_root(root), self.maxPathSum(root))
            if root is None:
                return 0, float("-inf")
            x, y = double(root.left)
            a, b = double(root.right)
            
            return root.val + max(x,a,0), max(y, b, (root.val + max(0, x) + max(0,a)))
    
        m, n = double(root)   
        return n 
    

    The function "double" returns two values 1) maximum sum of path starting from the root node and going down(max_path_from_root(root)) 2) The answer (what we want: self.maxPathSum(root)). Then these two values have recursive relations:

    1. max_path_from_root(root) = root.val + max(max_path_from_root(root.left), max_path_from_root(root.right), 0)
    2. self.maxPathSum(root) = max(self.maxPathSum(root.left), self.maxPathSum(root.right), root.val + max(0, max_path_from_root(root.left)) + max(0, max_path_from_root(root.right))
      Note that the first two terms are the case the maximum path does not go through the root node. The last case is when it goes through the root node.

Log in to reply
 

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