CODEWITHSUNDEEP
javaalgorithmrecursionbinary-tree
Spindoctor
Spindoctor

Reputation: 471

Binary Tree Maximum Path Sum Algorithm

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);
    }
}

Upvotes: 1

Views: 1022

Answers (3)

user22391347
user22391347

Reputation: 

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..

Upvotes: 0

Suman
Suman

Reputation: 868

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);
    }
}

Upvotes: 3

Emma
Emma

Reputation: 27723

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 analysis1, 2.

Upvotes: 3

Related Questions