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