Leetcode: 124. Binary Tree Maximum Path Sum

Problem Statement

Understand the Problem

Find the maximum path (sum of vertex values) in a tree.

Devise a plan

Pattern: Find optimal path in a tree by Building the solution as you process the input. Be \(u\) a node in the tree. Find the maximum path starting from the left \(l\) and from the right \(r\) of \(u\). The maximum path starting from \(u\) is either \(val(u)\), \(val(u)+l\) or \(val(u)+r\). To compute the final answer, we still have to consider \(u\) as the root of the maximum path: \(val(u)+l+r\). Time complexity is \(O(n)\) and space complexity is \(O(depth)\).

Carry out the plan

# 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
class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        def dfs(u):
            if u is None:
                return (0, float("-inf"))
            al, ar = dfs(u.left)
            bl, br = dfs(u.right)
            return (
                max(al, bl, 0) + u.val,
                max(ar, br, max(al, 0) + u.val + max(bl, 0)),
            )

        return max(dfs(root))

# 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
class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        def dfs(node):
            if node is None:
                return (0, float("-inf"))
            l = dfs(node.left)
            r = dfs(node.right)
            return (
                node.val + max(l[0], r[0], 0),
                max(max(l[0], 0) + node.val + max(r[0], 0), max(l[1], r[1])),
            )

        return max(dfs(root))

Common mistakes