LeetCode 124: Binary Tree Maximum Path Sum Solution

Master LeetCode problem 124 (Binary Tree Maximum Path Sum), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

124. Binary Tree Maximum Path Sum

Hard

Dynamic Programming Tree Depth-First Search Binary Tree

Problem Explanation

Explanation

To find the maximum path sum in a binary tree, we can use a recursive approach where at each node, we calculate the maximum path sum that includes the current node. We can calculate this by considering the maximum path sum that includes the left child, the maximum path sum that includes the right child, and the sum of the current node itself (if the paths from left and right child are positive).

For each node, we return the maximum path sum that includes that node in the path to its parent.

Time Complexity: O(n) where n is the number of nodes in the tree. Space Complexity: O(h) where h is the height of the tree.

Solution Code

class Solution {
    int maxSum = Integer.MIN_VALUE;
    
    public int maxPathSum(TreeNode root) {
        calculateMaxSum(root);
        return maxSum;
    }
    
    private int calculateMaxSum(TreeNode node) {
        if (node == null) {
            return 0;
        }
        
        int leftSum = Math.max(0, calculateMaxSum(node.left));
        int rightSum = Math.max(0, calculateMaxSum(node.right));
        
        int nodeSum = node.val + leftSum + rightSum;
        
        maxSum = Math.max(maxSum, nodeSum);
        
        return node.val + Math.max(leftSum, rightSum);
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 124 (Binary Tree Maximum Path Sum)?

This page provides optimized solutions for LeetCode problem 124 (Binary Tree Maximum Path Sum) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 124 (Binary Tree Maximum Path Sum)?

The time complexity for LeetCode 124 (Binary Tree Maximum Path Sum) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 124 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 124 in Java, C++, or Python.

Back to LeetCode Solutions