LeetCode 124. Binary Tree Maximum Path Sum

Question

I am trying to solve LeetCode problem 124. 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.

Constraints:

The number of nodes in the tree is in the range [1, 3 * 10⁴].

-1000 <= Node.val <= 1000

This is my code:

class Solution {
    public int maxPathSum(TreeNode root) {
        int[] max= new int[1];
        int res = dia(root, max);
        return max[0];       
    }
 
   public static int dia(TreeNode root,int[] max){
        if(root==null){
            return 0;
        }
        int lh = Math.max(0,dia(root.left, max));
        int rh =  Math.max(0,dia(root.right, max));
        max[0] = Math.max(max[0], lh+rh+root.val);
        return root.val +  Math.max(lh,rh);
    } 
}

For the input [-3] (which is a tree with just one node, having the value -3), my code returns 0, but the expected answer is -3.

How to account for this particular test case?

I am simply taking the max of 0 and the recursive calls to discount negative node values.

Since it doesn't make sense to add a negative value, I decided to take max of 0 and the recursive calls root.left, similarly for 0 and root.right.

But now I don't know how to go about a single node with negative value.

How should I adapt my code to cover such cases?

trincot · Accepted Answer · 2024-01-24 19:30:10Z

Since it doesn't make sense to add a negative value, I decided to take max of 0 and the recursive calls root.left...

The idea to take the max of 0 and the returned value is fine.

now I don't know how to go about a single node with negative value

The problem is not with taking the max of 0 and the returned values from recursion, but with the next statement where you take the max of max[0] and the path sum that includes root.val. For the failing case, that means that the negative value of the single node can never win from the 0 that you have initialised max[0] with at the start of your algorithm. But realise that this initialisation value of 0 does not correspond to any realistic path.

The correction is straightforward: don't initialise max[0] with 0, but either with an extreme negative value:

        int[] max = {Integer.MIN_VALUE};

or with a realistic value, which could be root.val (representing a path with only that node):

        int[] max = {root.val};

Both will make the code produce the correct value also when a negative value is expected.

Note that the second solution uses the given information that the given tree will not be empty.

Collectives™ on Stack Overflow

LeetCode 124. Binary Tree Maximum Path Sum

Example 1:

Constraints:

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

Example 1:

Constraints:

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related