124. Binary Tree Maximum Path Sum
124. Binary Tree Maximum Path Sum
搞一个全局变量，存结果，一个辅助函数，返回当前节点的一条路径的最大和，是左右子节点最大值加上当前节点，过程中要更新全局变量
class Solution(object):
def maxPathSum(self, root):
"""
:type root: TreeNode
:rtype: int
"""
self.res = float('-inf')
self.helper(root)
return self.res
def helper(self, root):
if root == None:
return 0
left = max(0, self.helper(root.left))
right = max(0, self.helper(root.right))
self.res = max(left + right + root.val, self.res)
return max(left, right) + root.val
网友评论