leetcode-124 Binary Tree Maximum Path Sum

[124] Binary Tree Maximum Path Sum

Key Concept: DFS with Global Max - At each node, calculate max path sum through that node. The path can include left subtree + node + right subtree. Return to parent the max single-side path (node + max(left, right, 0)).

Pattern: Tree recursion with global state tracking.

# A path in a binary tree is a sequence of nodes where each pair of adjacent
# nodes has an edge. A path may start and end at any node and doesn't have to
# go through the root. The path sum is the sum of node values in the path.
# Given the root, return the maximum path sum of any non-empty path.
#
# Example 1:
# Input: root = [1,2,3]
# Output: 6
# Explanation: Path is 2 -> 1 -> 3
#
# Example 2:
# Input: root = [-10,9,20,null,null,15,7]
# Output: 42
# Explanation: Path is 15 -> 20 -> 7
#
# Constraints:
# - Number of nodes in range [1, 3 * 10^4]
# - -1000 <= Node.val <= 1000

# 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:
        self.max_sum = float('-inf')

        def max_gain(node):
            """
            Returns: max path sum from this node going down (to parent)
            Side effect: updates global max_sum considering paths through this node
            """
            if not node:
                return 0

            # Recursively get max gain from left and right subtrees
            # Use max with 0 to ignore negative paths
            left_gain = max(max_gain(node.left), 0)
            right_gain = max(max_gain(node.right), 0)

            # Path through current node (left + node + right)
            path_sum_through_node = left_gain + node.val + right_gain

            # Update global maximum
            self.max_sum = max(self.max_sum, path_sum_through_node)

            # Return max path sum going down from this node
            # (can only choose one side to connect to parent)
            return node.val + max(left_gain, right_gain)

        max_gain(root)
        return self.max_sum

# Time Complexity: O(n) - visit each node once
# Space Complexity: O(h) - recursion stack where h is height
#
# Key Insight:
# At each node, we consider two things:
# 1. Max path sum THROUGH this node (left + node + right)
#    - This updates our global answer
#    - This path CAN'T be returned to parent (uses both sides)
#
# 2. Max path sum FROM this node (going down to parent)
#    - node + max(left, right)
#    - This is what we return to allow parent to extend the path
#    - Can only choose ONE side
#
# Why max with 0?
# - Negative paths don't help, so we can choose not to include them
#
# Visualization:
#       10
#      /  \
#     2    10
#    / \     \
#   20  1   -25
#              \
#               3
#
# At node 2: left_gain=20, right_gain=1
# - path through 2: 20 + 2 + 1 = 23
# - return to parent: 2 + 20 = 22
#
# AirBnB: Tests recursion and global state management