# Python recursive solution get Runtime Error but not TLE?

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

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

• This post is deleted!

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