Binary Tree Maximum Path Sum

此题应该是二叉树的题目中最难的一道了，代码简单，但是思维复杂，嵌套了多个比较，首先理清题目要求，这里要求的所谓路径是任意两个点的路径，这种路径导致了我们遍历每一个点时，这个点有两种总体情况需要我们求。

第一种是以这个点为顶点的路径和，那也就是说是以这个顶点左右子树的若干点组成的路径

第二种是这个点只是路径中的一个普通点而不是顶点，这个时候我们只要这个点的左子树或者右子树中的一个路径的最大值就行

这样代码就很简单了

import sys

class Solution(object):
    result = -sys.maxint
    def maxPathSum(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        self.helper(root)
        return self.result

    def helper(self, root):
        if not root:
            return 0
        else:
            sinLeft, sinRight = self.helper(root.left), self.helper(root.right)
            maxSingle = max(max(sinLeft, sinRight) + root.val, root.val)
            maxTop = max(max(maxSingle, sinLeft + sinRight + root.val), root.val)
            self.result = max(self.result, maxTop)
            return maxSingle