Binary Tree Maximum Path Sum

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.

The path sum of a path is the sum of the node's values in the path.

Given the root of a binary tree, return the maximum path sum of any non-empty path.

Solution

• The algorithm performs a post-order traversal (left, right, root) of the tree. At each node, it calculates the maximum sum path that passes through the node and possibly extends to its left or right children.
• The key insight is that the path can either "pass through" the current node (using both its left and right children) or "extend down" to either of its children (but not both).
• The global maxSum is updated whenever a path sum that includes the current node as the highest point is greater than the previously recorded maximum.
• Finally, the algorithm returns maxSum, which holds the largest sum of any path in the tree.

class Solution {
    private int maxSum;

    public int maxPathSum(TreeNode root) {
        maxSum = Integer.MIN_VALUE; // Initialize to the smallest integer value
        maxPathSumHelper(root);
        return maxSum;
    }

    private int maxPathSumHelper (TreeNode node) {
        if (node == null) {
            return 0;
        }

        // Recursively get the maximum path sum of the left and right subtrees

        // Only add positive contributions
        int leftMax = Math.max(maxPathSumHelper(node.left), 0); 

        // Only add positive contributions
        int rightMax = Math.max(maxPathSumHelper(node.right), 0); 

        // Calculate the maximum path sum with the current node as the highest node
        int currentMax = node.val + leftMax + rightMax;

        // Update the global maximum path sum
        maxSum = Math.max(maxSum, currentMax);

        // Return the maximum path sum starting from the current node
        return node.val + Math.max(leftMax, rightMax);
    }
}