Different result in local machine and OJ


  • 0
    J

    Below is my solution for "Binary Tree Maximum Path Sum" in python.
    I got the wrong result from OJ while I tested the same code in my local machine. It works fine.

    Is there anyone help look into my code and find out the problem?

    Definition for a binary tree node

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

    class Solution:
    def init(self):
    self.maxSumInTree = 0

    # @param root, a tree node
    # @return an integer
    def maxPathSum(self, root):
        if root is None:
            return 0
        
        self.maxSumInTree = root.val
        
        maxSumInTree = self.maxTreeSum(root)
    
        return self.maxSumInTree
    
    def maxTreeSum(self, node):
        if node is None:
            return 0,0
        
        sumL = sumR = 0
        if not node.left is None:
            sumLL, sumLR = self.maxTreeSum(node.left)
            sumL = max(sumLL, sumLR) + node.left.val
        if not node.right is None:
            sumRL, sumRR = self.maxTreeSum(node.right)
            sumR = max(sumRL, sumRR) + node.right.val
            
        #calculate max Path include this Node
        maxNodePathValue = max(max(max(sumL + node.val, sumR+node.val), sumL+sumR+node.val), node.val)
        
        if self.maxSumInTree < maxNodePathValue:
            self.maxSumInTree = maxNodePathValue
        
        return sumL, sumR

  • 0
    D

    There is a bug in your code:

    sumL = max(sumLL, sumLR) + node.left.val
    

    and

    sumR = max(sumRL, sumRR) + node.right.val
    

    Change them to:

    sumL = max(max(sumLL, sumLR) + node.left.val, node.left.val)
    

    and

    sumR = max(max(sumRL, sumRR) + node.right.val, node.right.val)
    

    respectively, the code passed the tests


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.