Binary Tree Maximum Path Sum Algorithm

Question

I am new to recursion and binary trees. I am trying to solve this problem on leetcode.

To find maximum sum path is like finding maximum path between any two nodes, that path may or may not pass through the root; except that with max sum path we want to track sum instead of path length.

My algorithm is passing 91/93 test cases and I just can't figure out what I am missing. Can anyone please provide some direction?

class Solution {
    private int sum = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        maxPathSumHelper(root);
        if(root.left != null){
            maxPathSumHelper(root.left);
        }
        if(root.right != null){
            maxPathSumHelper(root.right);
        }
        
        return sum;
    }
    public int  maxPathSumHelper(TreeNode root){
        if(root ==  null){
            return 0;
        }
        //check left sum
        int leftValue = root.val + maxPathSumHelper(root.left);
        if(leftValue > sum){
            sum = leftValue;
        }
        //check right sum
        int rightValue = root.val + maxPathSumHelper(root.right);
        if(rightValue > sum){
            sum = rightValue;
        }
        //check if root value is greater 
        if(root.val > sum){
            sum = root.val;
        }
        //check if right and left value is the greatest
        if((leftValue + rightValue - (2 * root.val) )+ root.val > sum){
            sum = (leftValue + rightValue - (2 * root.val)) + root.val;
        }
        return Math.max(leftValue, rightValue);
    }
}

To me the task looks more like a max-sum-subtree, not a path. — Ridcully
– Ridcully, Commented Aug 9, 2020 at 20:05

Emma Marcier · Accepted Answer · 2020-08-10 01:14:35Z

Try

class Solution {
    private int sum = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        maxPathSumHelper(root);

        if (root.left != null) {
            maxPathSumHelper(root.left);

        } else if (root.right != null) {
            maxPathSumHelper(root.right);

        }

        return sum;
    }
    public int  maxPathSumHelper(TreeNode root) {
        if (root ==  null) {
            return 0;
        }

        //check left sum
        int leftValue = root.val + maxPathSumHelper(root.left);

        if (leftValue > sum) {
            sum = leftValue;
        }

        //check right sum
        int rightValue = root.val + maxPathSumHelper(root.right);

        if (rightValue > sum) {
            sum = rightValue;
        }

        //check if root value is greater
        if (root.val > sum) {
            sum = root.val;
        }

        //check if right and left value is the greatest
        if ((leftValue + rightValue - (2 * root.val) ) + root.val > sum) {
            sum = (leftValue + rightValue - (2 * root.val)) + root.val;
        }

        return Math.max(Math.max(leftValue, rightValue), root.val);
    }
}

Emma Marcier · Accepted Answer · 2020-08-09 19:47:07Z

3

I guess we can a bit simplify our statements here.

This'll simply get accepted:

public final class Solution {
    int max;

    public final int maxPathSum(final TreeNode root) {
        max = Integer.MIN_VALUE;
        traverse(root);
        return max;
    }

    private final int traverse(final TreeNode node) {
        if (node == null)
            return 0;
        final int l = Math.max(0, traverse(node.left));
        final int r = Math.max(0, traverse(node.right));
        max = Math.max(max, l + r + node.val);
        return Math.max(l, r) + node.val;
    }
}

References

For additional details, please see the Discussion Board which you can find plenty of well-explained accepted solutions in there, with a variety of languages including efficient algorithms and asymptotic time/space complexity analysis^{1, 2}.

answered Aug 9, 2020 at 19:47

Emma Marcier

27.8k12 gold badges49 silver badges71 bronze badges

3 Comments

Ridcully Over a year ago

This does not seem to take the negative node values into account, does it?

Spindoctor Over a year ago

@Emma thank you for simplifying my complicated statements and taking the time to provide the steps. Although I see a similarity in the logic of the statements, I am still trying to figure out what comparison I am missing that is throwing the algorithm off. can you perhaps help me with this - please and thank you.

Spindoctor Over a year ago

@Suman thanks I think I was missing the fact that either the leftsum or rightsum or left + right + root should be returned. I think i get it now. Thank you both Emma and Suman. Both solutions help me understand.

user22391347 · Accepted Answer · 2023-09-15 11:01:28Z

0

class Solution:
 def numDecodings(self, s: str) -> int:
   if s[0] == '0':
    return 0

   dp = [[0, 0] for i in range(len(s) + 1)]

   dp[0][0] = 1
   dp[1][0] = 1

   for i in range(1, len(s)):
    # zero must be second
    if s[i] == '0':
      if s[i-1] not in ['1', '2']:
        return 0
      dp[i+1] = [0, dp[i][0]]

    elif '00' < s[i-1:i+1] < '27' and s[i-1] != '0':
      dp[i+1] = [sum(dp[i]), sum(dp[i-1])]

    else:
      dp[i+1] = [sum(dp[i]), 0]

  return sum(dp[len(s)])

Try this code using Python 3 format at Leetcode you will passed..

answered Sep 15, 2023 at 11:01

user22391347

Collectives™ on Stack Overflow

Binary Tree Maximum Path Sum Algorithm

3 Answers 3

Comments

References

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

References

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related