Binary Tree Maximum Path Sum

1class Solution {
2    private int maxSum = Integer.MIN_VALUE;
3
4    public int maxPathSum(TreeNode root) {
5        calculateMaxGain(root);
6        return maxSum;
7    }
8
9    private int calculateMaxGain(TreeNode node) {
10        if (node == null) return 0;
11
12        // Calculate max gain from left and right (discard negative)
13        int leftGain = Math.max(calculateMaxGain(node.left), 0);
14        int rightGain = Math.max(calculateMaxGain(node.right), 0);
15
16        // Calculate path sum through this node
17        int currentMaxPath = node.val + leftGain + rightGain;
18
19        // Update global maximum
20        maxSum = Math.max(maxSum, currentMaxPath);
21
22        // Return gain to parent
23        return node.val + Math.max(leftGain, rightGain);
24    }
25}