Reputation: 117
Unable to keep a track of the variable maxSum, after recursive calls it keeps resetting back to 0, despite passing it as a parameter in calls. The function maxPathSum should return 11 but it's returning 0.
class TreeNode:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
def maxPathSum(node):
sums = []
maxPath = []
maxSum = 0
recursiveSum(node, 0, maxSum, sums)
return maxSum
def recursiveSum(node, ssum, maxSum, sums):
if node == None:
return
if maxSum < ssum + node.val and node.left == None and node.right == None:
maxSum = ssum + node.val
sums.append(maxSum)
# traverse left subtree
recursiveSum(node.left, ssum + node.val, maxSum, sums)
# traverse right subtree
recursiveSum(node.right, ssum + node.val, maxSum, sums)
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(7)
root.right.right = TreeNode(6)
print(maxPathSum(root))
Upvotes: 1
Views: 506
Reputation: 2136
You can achieve your goal by one of the following two modifications.
Since you build a list from the maxSum
values, you can simply change the last line of your maxPathSum
function so:
def maxPathSum(node):
sums = []
maxPath = []
maxSum = 0
recursiveSum(node, 0, maxSum, sums)
return max(sums)
Or you can use the maxSum
variable, but for this you must do some small modifications in both functions:
def maxPathSum(node):
sums = []
maxPath = []
maxSum = 0
maxSum=recursiveSum(node, 0, maxSum, sums)
return maxSum
def recursiveSum(node, ssum, maxSum, sums):
if node == None:
return
if maxSum < ssum + node.val and node.left == None and node.right == None:
maxSum = ssum + node.val
sums.append(maxSum)
# traverse left subtree
s=recursiveSum(node.left, ssum + node.val, maxSum, sums)
if s!=None: maxSum=max(maxSum,s)
# traverse right subtree
s=recursiveSum(node.right, ssum + node.val, maxSum, sums)
if s!=None: maxSum=max(maxSum,s)
return maxSum
Upvotes: 2