124 Binary Tree Maximum Path Sum
124. Binary Tree Maximum Path Sum
题目: https://leetcode.com/problems/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
其实开始的时候我想当然的用了很傻的方法，并且是错误的，因为这样当[-10,9,20,null,null,15,7]的时候我们会取所有的点，返回41，然而我们可以取到42的， 即15+7+20
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))
