124. Binary Tree Maximum Path Sum

這題比較簡(jiǎn)單，也是屬于老題目了，唯一要注意的地方就是每個(gè)值要和0比較一下，因?yàn)榭梢圆贿x這個(gè)值。

# 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