LeetCode Hard – 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.

Example 1:

Input: root = [1,2,3]

Output: 6

Explanation: The optimal path is 2 -> 1 -> 3 with a path sum of 2 + 1 + 3 = 6.

Example 2:

Input: root = [-10,9,20,null,null,15,7]

Output: 42

Explanation: The optimal path is 15 -> 20 -> 7 with a path sum of 15 + 20 + 7 = 42.

Constraints:

• The number of nodes in the tree is in the range [1, 3 * 104].
• -1000 <= Node.val <= 1000

Java Solution

To solve this problem, you can use a recursive approach to traverse the binary tree and calculate the maximum path sum for each node. At each node, you need to consider the maximum sum that includes the current node (i.e., the node is part of the path), and the maximum sum that goes through the current node (i.e., the path goes from the left subtree to the current node to the right subtree).

Here’s the Java solution:

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) {
        this.val = val;
    }
}

public class BinaryTreeMaximumPathSum {
    private int maxPathSum = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        calculateMaxPathSum(root);
        return maxPathSum;
    }

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

        // Calculate the maximum path sum for the left and right subtrees
        int leftMax = Math.max(0, calculateMaxPathSum(node.left));
        int rightMax = Math.max(0, calculateMaxPathSum(node.right));

        // Update the global maximum path sum considering the current node
        maxPathSum = Math.max(maxPathSum, leftMax + rightMax + node.val);

        // Return the maximum path sum that includes the current node (i.e., the node is part of the path)
        return Math.max(leftMax, rightMax) + node.val;
    }

    public static void main(String[] args) {
        BinaryTreeMaximumPathSum solution = new BinaryTreeMaximumPathSum();

        // Example 1
        TreeNode root1 = new TreeNode(1);
        root1.left = new TreeNode(2);
        root1.right = new TreeNode(3);
        System.out.println(solution.maxPathSum(root1));  // Output: 6

        // Example 2
        TreeNode root2 = new TreeNode(-10);
        root2.left = new TreeNode(9);
        root2.right = new TreeNode(20);
        root2.right.left = new TreeNode(15);
        root2.right.right = new TreeNode(7);
        System.out.println(solution.maxPathSum(root2));  // Output: 42
    }
}

This Java code defines a TreeNode class for the tree nodes and a BinaryTreeMaximumPathSum class with the maxPathSum method. The calculateMaxPathSum method is a recursive helper function to calculate the maximum path sum for each node. The maxPathSum variable is used to store the global maximum path sum. The provided test cases demonstrate its usage.

Python Solution

Here’s the equivalent Python solution for finding the maximum path sum in a binary tree:

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

class BinaryTreeMaximumPathSum:
    def __init__(self):
        self.maxPathSum = float('-inf')

    def maxPathSum(self, root):
        self.calculateMaxPathSum(root)
        return self.maxPathSum

    def calculateMaxPathSum(self, node):
        if not node:
            return 0

        # Calculate the maximum path sum for the left and right subtrees
        left_max = max(0, self.calculateMaxPathSum(node.left))
        right_max = max(0, self.calculateMaxPathSum(node.right))

        # Update the global maximum path sum considering the current node
        self.maxPathSum = max(self.maxPathSum, left_max + right_max + node.val)

        # Return the maximum path sum that includes the current node (i.e., the node is part of the path)
        return max(left_max, right_max) + node.val

# Test cases
solution = BinaryTreeMaximumPathSum()

# Example 1
root1 = TreeNode(1)
root1.left = TreeNode(2)
root1.right = TreeNode(3)
print(solution.maxPathSum(root1))  # Output: 6

# Example 2
root2 = TreeNode(-10)
root2.left = TreeNode(9)
root2.right = TreeNode(20)
root2.right.left = TreeNode(15)
root2.right.right = TreeNode(7)
print(solution.maxPathSum(root2))  # Output: 42

This Python code uses a similar structure as the Java solution. The TreeNode class represents the tree nodes, and the BinaryTreeMaximumPathSum class contains the maxPathSum method. The calculateMaxPathSum method is a recursive helper function to calculate the maximum path sum for each node. The maxPathSum attribute is used to store the global maximum path sum. The provided test cases demonstrate its usage.