LeetCode 124 Binary Tree Maximum Path Sum - Implementation

Post-order traversal. Track max path sum globally, return gain upward.

function maxPathSum(root): result = float('-inf')

def maxGain(node):
    nonlocal result
    if not node:
        return 0
    leftGain = max(maxGain(node.left), 0)
    rightGain = max(maxGain(node.right), 0)
    pathSum = node.val + leftGain + rightGain
    result = max(result, pathSum)
    return node.val + max(leftGain, rightGain)

maxGain(root)
return result

$O(n)$ time, $O(h)$ space.