LeetCode #124 Hard

Binary Tree Maximum Path Sum

Find the maximum sum over any path (any node to any node, no revisits).

treedfsdp

02

Intuition

💡

Like diameter, but weighted and with negatives. Each node answers two different questions: 'best downward path starting here' (what the parent can use — one branch only) and 'best path bending here' (left gain + node + right gain — a candidate answer). Negative branches contribute 0: better to not extend.

03

Approach

1

Gain = usable path

gain(node) = node.val + max(gain(left), gain(right), both clamped at 0). A parent can extend through only one child.

2

Bend = candidate

At each node, leftGain + node.val + rightGain uses both branches — legal as a full path, illegal to pass upward. Track its max globally.

3

Clamp negatives to zero

max(gain, 0) implements 'drop a branch that hurts' — the crux with negative values.

04

Solution & live demo

python

▶1class Solution:
▶2    def maxPathSum(self, root):
▶3        self.best = float("-inf")
▶4        def gain(node):
▶5            if not node: return 0
▶6            l = max(gain(node.left), 0)
▶7            r = max(gain(node.right), 0)
▶8            self.best = max(self.best, node.val + l + r)
▶9            return node.val + max(l, r)
▶10        gain(root)
▶11        return self.best

05

Edge cases

All negative values

Clamps make gains 0, but the bend at each single node still records node.val — the answer is the largest (least negative) node.

Single node

Bend = its value.

06

Complexity

Time

O(n)

Space

O(h)

One post-order pass, two roles per node.