LeetCode 124: Binary Tree Maximum Path Sum — Step-by-Step Visual Trace

#leetcode #python #algorithms #datastructures

Hard — Binary Tree | Depth-First Search | Recursion | Dynamic Programming

The Problem

Find the maximum sum of any path in a binary tree, where a path is defined as any sequence of nodes connected by parent-child relationships. The path can start and end at any nodes in the tree.

Approach

Use recursive depth-first search to calculate the maximum path sum ending at each node. At each node, consider the maximum contribution from left and right subtrees (ignoring negative contributions), update the global maximum with the path passing through the current node, and return the maximum single-branch path sum.

Time: O(n) · Space: O(h)

Code

class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        def maxPathSumHelper(node):
            if not node:
                return 0

            left_sum = max(0, maxPathSumHelper(node.left))
            right_sum = max(0, maxPathSumHelper(node.right))

            self.max_sum = max(self.max_sum, left_sum + right_sum + node.val)

            return max(left_sum, right_sum) + node.val

        self.max_sum = float("-inf")
        maxPathSumHelper(root)

        return self.max_sum