Leetcode # 124. Binary Tree Maximum Path Sum

https://leetcode.com/problems/binary-tree-maximum-path-sum/

Solution

Time Complexity: O(len(tree))
Space Complexity: O(len(tree))
(The input and output generally do not count towards the space complexity.)

class Solution:
  def maxPathSum(self, root: Optional[TreeNode]) -> int:
    self.max_path_sum = root.val if root else 0
    def max_path_sum_from(root):
      if not root: return 0
      # ↓ because it will be early returned if root is a leaf
      max_path_sum = max(self.max_path_sum, root.val)
      if not root.left and not root.right: return root.val
      max_path_sum_from_left  = max_path_sum_from(root.left)
      max_path_sum_from_right = max_path_sum_from(root.right)
      max_path_sum_start_from_root  = max(root.val, 
                                          root.val + max_path_sum_from_left, 
                                          root.val + max_path_sum_from_right)
      self.max_path_sum = max(self.max_path_sum, 
                              root.val + max_path_sum_from_left \
                                       + max_path_sum_from_right, 
                              max_path_sum_start_from_root
                              )
      return max_path_sum_from_root
    max_path_sum_from(root)
    return self.max_path_sum

Refined Solution: Postorder Traversal

1. 後序巡訪 (postorder traversal) 每一個 node
2. 後序巡訪 (左子樹 → 右子樹 → 現節點) 的過程中
   計算「一端終止於左/右子樹根節點」的所有 path 中最大的 sum
3. 計算經過現節點的所有 path 中最大的 sum

Time Complexity: O(len(tree))
Space Complexity: O(len(tree))
(The input and output generally do not count towards the space complexity.)

class Solution:
  def maxPathSum(self, root: Optional[TreeNode]) -> int:
    self.max_path_sum = root.val if root else 0
    def find_max_path_sum_through(curr):
      if curr is None: return 0
      max_path_sum_through_left  = max(0, find_max_path_sum_through(curr.left))
      max_path_sum_through_right = max(0, find_max_path_sum_through(curr.right))
      self.max_path_sum = max(self.max_path_sum, \
                              curr.val + max_path_sum_through_left + max_path_sum_through_right)
      return curr.val + max(max_path_sum_through_left, max_path_sum_through_right)
    find_max_path_sum_through(root)
    return self.max_path_sum

Last Updated on 2024/04/27 by A1go