每个node的值可正可负, 参考了网上C++解法, 类变量Solution.maxSum用于记录最大路径和, 当level为0时返回它; maxPathSum(root)函数返回的是经过root的路径最大和, 可以只是root, 也可以是左子树某一部分+root或者root+右子树某一部分。这个函数是可以返回0的, 也就是说currRoot, currRoot+左子树, currRoot+右子树的值都小于等于0, 对max path sum没有贡献, 之后就不再考虑了。

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    # @param root, a tree node
    # @return an integer
    deep = 0

    def maxPathSum(self, root):
        if root == None:
            return 0
        if Solution.deep == 0: ＃ Solution.maxSum is set to infinitesimal every time when a new test case starts
            Solution.maxSum = -10 ** 10
        Solution.deep += 1
        vLeft = self.maxPathSum(root.left)
        vRight = self.maxPathSum(root.right)
        Solution.deep -= 1
        Solution.maxSum = max(root.val + vLeft + vRight, Solution.maxSum)
        if Solution.deep == 0:
            return Solution.maxSum
        return max(root.val + vLeft, root.val + vRight, 0)