Binary Tree Maximum Path Sum

Intuition

The trick is to separate two ideas: what a node can contribute to its parent versus what the best path through that node looks like. A node can only hand its parent a straight line going down one side, so the gain it returns is node.val plus the larger of its two children's gains (and we clamp a child's gain to zero when it is negative, since including a negative branch never helps). Meanwhile, the best path that peaks at this node may fan out through both children, so we form node.val + leftGain + rightGain and compare it against a running global maximum. Every node gets a chance to be the highest point of the answer path. A single post-order traversal computes both quantities in one pass.

Algorithm walkthrough

1. 1Keep a global best value, initialized so any real path can beat it.
2. 2Define gain(node): if the node is null, return 0 (a missing branch adds nothing).
3. 3Recursively compute leftGain and rightGain, replacing any negative result with 0.
4. 4Update best with node.val + leftGain + rightGain, the value of a path that bends through this node.
5. 5Return node.val + max(leftGain, rightGain) so the parent can extend a single straight branch.
6. 6Call gain(root) to populate best, then return best.

Implementation

class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        self.best = float('-inf')

        def gain(node: Optional[TreeNode]) -> int:
            if not node:
                return 0
            left = max(gain(node.left), 0)
            right = max(gain(node.right), 0)
            self.best = max(self.best, node.val + left + right)
            return node.val + max(left, right)

        gain(root)
        return self.best