Python recursive solution get Runtime Error but not TLE?


  • 0
    C

    I write a recursive solution in Python refer to a C++ recursive solution in "Discuss" page.
    But i got Runtime error but not TLE. Can anyone tell me why?
    Code is below:

    class Solution:
        # @param root, a tree node
        # @return an integer
        def maxPathSum(self, root):
            def rec(node, maxval):
                if node == None:
                    return 0,0
                l = max(0, rec(node.left, maxval)[0])
                r = max(0, rec(node.right, maxval)[0])
                maxval = max(maxval, l + r + node.val)
                return max(l, r)+node.val, maxval
            return rec(root, -2147483648)[1]
    

    I know recursive is not very efficient. So i wanted to solve this problem first and then optimize it.
    I can accept TLE, Runtime error is unexpected...


  • 0
    A

    When you want to update 'maxval', you should notice variable's scope. You can using mutable type just like list to do that.

    class Solution:
        # @param root, a tree node
        # @return an integer
        def maxPathSum(self, root):
            def rec(node, maxval):
                if node == None:
                    return (0,maxval[0])
                l = max(0, rec(node.left, maxval)[0])
                r = max(0, rec(node.right, maxval)[0])
                maxval[0] = max(maxval[0], l + r + node.val)
                return (max(l, r)+node.val, maxval[0])
            return rec(root, [-2147483648])[1]
    

    Update: About RE, I tried define rec as member func, it's OK. The code is below:

    class Solution:
        # @param root, a tree node
        # @return an integer
        def maxPathSum(self, root):
            return self.rec(root, [-2147483648])[1]
    
        def rec(self, node, maxval):
            if node == None:
                return (0,maxval[0])
            l = max(0, self.rec(node.left, maxval)[0])
            r = max(0, self.rec(node.right, maxval)[0])
            maxval[0] = max(maxval[0], l + r + node.val)
            return (max(l, r)+node.val, maxval[0])
    

    Actually, in the last solution, you can using the member variable to save your result rather than passing it to the rec function.


  • 0
    A
    This post is deleted!

Log in to reply
 

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