124. Binary Tree Maximum Path Sum

Description:

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.

The path sum of a path is the sum of the node's values in the path.

Given the root of a binary tree, return the maximum path sum of any non-empty path.

 

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
'''
[1] recursive approach)

idea::
  a
 b c
max_pathSum= max(a, ab, ac, bac)
so, compare all cases

code::
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        self.max_pathSum=-float(inf)
        
        self.curPathSum(root,self.max_pathSum)
        return self.max_pathSum
    
    def curPathSum(self, root, max_pathSum):
        if not root:
            return 0
        
        left_max=self.curPathSum(root.left,self.max_pathSum)
        right_max=self.curPathSum(root.right,self.max_pathSum)
        
        # max(a, ab, ac)
        tmp_max=max(max(left_max,right_max),0)+root.val
        
        # update
        self.max_pathSum=max(tmp_max, root.val+left_max+right_max, self.max_pathSum)
        
        return tmp_max
        
-T/C: O(n)
-S/C: O(h)
'''
class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        self.max_pathSum=-float(inf)
        
        self.curPathSum(root,self.max_pathSum)
        return self.max_pathSum
    
    def curPathSum(self, root, max_pathSum):
        if not root:
            return 0
        
        left_max=self.curPathSum(root.left,self.max_pathSum)
        right_max=self.curPathSum(root.right,self.max_pathSum)
        
        # max(a, ab, ac)
        tmp_max=max(max(left_max,right_max),0)+root.val
        
        # update
        self.max_pathSum=max(tmp_max, root.val+left_max+right_max, self.max_pathSum)
        
        return tmp_max