Problem #124: Binary Tree Maximum Path Sum

Intuition & Strategy Breakdown

Perform post-order DFS. At each node, return max gain obtainable starting from node (val + max(left_gain, right_gain, 0)), updating global max path sum with val + left + right.

Python Solution

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

        def get_gain(node):
            if not node:
                return 0
            
            left_gain = max(get_gain(node.left), 0)
            right_gain = max(get_gain(node.right), 0)
            
            current_max_path = node.val + left_gain + right_gain
            self.max_sum = max(self.max_sum, current_max_path)
            
            return node.val + max(left_gain, right_gain)

        get_gain(root)
        return self.max_sum

Java Solution

class Solution {
    private int maxSum = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        getGain(root);
        return maxSum;
    }

    private int getGain(TreeNode node) {
        if (node == null) return 0;
        int leftGain = Math.max(getGain(node.left), 0);
        int rightGain = Math.max(getGain(node.right), 0);
        int currentMaxPath = node.val + leftGain + rightGain;
        maxSum = Math.max(maxSum, currentMaxPath);
        return node.val + Math.max(leftGain, rightGain);
    }
}