Python Recursive solution with explanation O(n) Post-order traversal.


  • 1
    Y

    The maximum path sum can either be in the left subtree or the right subtree so using the post-order traversal is good.

    • because the maximum will not always go through root, at each node you always check if the sum of the left and right and current node val and store the maximum

    • at each node, you always return the current node value + the max of left subtree or right subtree
      or the node value itself if it's bigger then the left or right subtree.

    class Solution(object):
        max_val = -10000
    
        def max_path(self,root):
            if root:
                left = self.max_path(root.left)
                right = self.max_path(root.right)
    
                self.max_val = max(self.max_val, max(left,right)+root.val,left+right+root.val,root.val)
                #print "at node ", root.val , "left is " , left , "right is " , right, "returning: ", max(max(left,right)+root.val,root.val)
                #print "max: ", self.max_val
                return max(max(left,right)+root.val,root.val)
            else:
                return 0
                    
        def maxPathSum(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            self.max_path(root)
            return self.max_val
    

  • 0
    G
    This post is deleted!

Log in to reply
 

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