124. Binary Tree Maximum Path Sum
这题比较简单，也是属于老题目了，唯一要注意的地方就是每个值要和0比较一下，因为可以不选这个值。
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def maxPathSum(self, root):
"""
:type root: TreeNode
:rtype: int
"""
res, _ = self.helper(root)
return res
def helper(self, root):
if not root:
return -sys.maxint, -sys.maxint # max length and single length
left_max, left_single = self.helper(root.left)
right_max, right_single = self.helper(root.right)
root_max = max(left_max, right_max, max(left_single,0)+max(right_single,0)+root.val)
root_single = max(left_single, right_single, 0) + root.val
return root_max, root_single
