124.BinaryTreeMaximumPathSum_zheyuuu.py

# Source : https://leetcode.com/problems/binary-tree-maximum-path-sum
# Author : zheyuuu
# Date : 2020-08-05

##################################################################################################### 
#
# Given a non-empty binary tree, find the maximum path sum.
# 
# For this problem, a path is defined as any sequence of nodes from some starting node to any node in 
# the tree along the parent-child connections. The path must contain at least one node and does not 
# need to go through the root.
# 
# Example 1:
# 
# Input: [1,2,3]
# 
# 1
# / \
# 2 3
# 
# Output: 6
# 
# Example 2:
# 
# Input: [-10,9,20,null,null,15,7]
# 
# -10
# / \
# 9 20
# / \
# 15 7
# 
# Output: 42
# 
#####################################################################################################

classSolution:
defmaxPathSum(self, root: TreeNode) ->int:
self.ans=float("-inf")
self.helper(root)
returnself.ans

defhelper(self, node):
ifnotnode:
return0
left=self.helper(node.left)
right=self.helper(node.right)
lval=leftifleft>=0else0
rval=rightifright>=0else0
self.ans=max(node.val+lval+rval, self.ans)
returnmax(node.val+lval, node.val+rval)