Leetcode 124. Binary Tree Maximum Path Sum

这道题是给一个树，求任意起始点，终止点的最大路径。用dfs，很有意思的题。首先我们有一个变量，记录遍历树得到的最大路径。然后在遍历过程中，我们的返回值是以当前节点为终点的最大路径。以当前节点为终点的最大路径的值就是当前节点的值加上左子树最大路径的值或右子树最大路径的值，看哪边大，而且左子树右子树结果必须大于0.要不然不用加。然后遍历过程中，最大路径就是当前节点加上左边和右边（也得满足大于0）。
python代码：

import sys
class Solution:
    def maxPathSum(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        self.maxsum = -sys.maxsize
        self.helper(root)
        return self.maxsum
    
    def helper(self, node):
        if not node:
            return 0
        leftsum = self.helper(node.left)
        rightsum = self.helper(node.right)
        totalsum = node.val
        if leftsum > 0:
            totalsum += leftsum
        if rightsum > 0:
            totalsum += rightsum
        if totalsum > self.maxsum:
            self.maxsum = totalsum
        return node.val + max(max(leftsum, rightsum), 0)