124 Binary Tree Maximum Path Sum

124. Binary Tree Maximum Path Sum

Hard

class Solution(object):

def maxPathSum(self, root):
"""
:type root: TreeNode
:rtype: int
"""
self.global_max = root.val if root else 0
self.findmax(root)
return self.global_max

def findmax(self, node):
if not node:
return 0

left = self.findmax(node.left)
left = left if left > 0 else 0

right = self.findmax(node.right)
right = right if right > 0 else 0
# 这句是精髓，只要判断出当前这个点作为root的path更长，就更新一下
self.global_max = max(left + right + node.val, self.global_max)
# 这里是因为sub_path只能为一条边，不然跟上面的root组合起来就不是path了
return max(left, right) + node.val


class Solution(object):
def maxPathSum(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root:
return 0
if not root.left and not root.right:
return root.val
if not root.left:
return max(root.val, root.val+self.maxPathSum(root.right))
if not root.right:
return max(root.val, root.val+self.maxPathSum(root.left))
return max(root.val,
root.val+self.maxPathSum(root.right),
root.val+self.maxPathSum(root.left),
root.val+self.maxPathSum(root.left)+self.maxPathSum(root.right))


apachecn/AiLearning