binary_tree_maximum_path_sum.py

from typing import Optional


class TreeNode:
    """LeetCode provides this class; repeated here so the file runs standalone."""

    def __init__(self, val: int = 0, left: "Optional[TreeNode]" = None,
                 right: "Optional[TreeNode]" = None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    """LeetCode #124 - Binary Tree Maximum Path Sum (Hard)
    https://leetcode.com/problems/binary-tree-maximum-path-sum/

    A path is any sequence of nodes connected by edges, going in any direction
    but visiting each node at most once. It need not pass through the root.
    Return the maximum sum of node values along such a path. Values may be
    negative.
    """

    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        """One DFS returning "best downward path", with a global best on the side.

        This is #543 (Diameter) with sums instead of edge counts, plus one extra
        wrinkle - and both ideas are worth separating clearly:

        1. **Two different quantities.** Every path has a single topmost node.
           At that node the best path *turning* there is
           `node.val + left_gain + right_gain` - it uses both children. But what
           the parent can reuse is only a path going *straight down* through one
           child: `node.val + max(left_gain, right_gain)`. A path that forked
           cannot be extended upward without revisiting the node. So the
           recursion returns the second quantity and records the first in
           `best`.

        2. **Negative subtrees get dropped.** `max(gain, 0)` says: if a branch
           contributes a negative sum, take nothing from it instead. Attaching a
           net-negative subtree can never improve a path, and cutting it is
           always allowed since the node itself is enough of a path.

        `best` starts at -inf, not 0 - the path must contain at least one node,
        so a tree of only negative values answers with its largest value.

        Time:  O(n) - each node is visited once.
        Space: O(h) - recursion depth.
        """
        best = float("-inf")

        def gain(node: Optional[TreeNode]) -> int:
            """Max sum of a path that starts at `node` and goes strictly down."""
            nonlocal best
            if node is None:
                return 0

            left = max(gain(node.left), 0)     # negative branch -> take nothing
            right = max(gain(node.right), 0)

            # Path turning at this node - uses both sides, cannot go higher.
            best = max(best, node.val + left + right)

            # Reported upward - one side only, so the parent can extend it.
            return node.val + max(left, right)

        gain(root)
        return best