思路

这道题目非常考验对递归的理解。

1. 经过该点的有左右孩子的子树的max sum。在这种情况下，这个局域max path sum是不可以给root的夫节点使用的。

2. 经过该点只有左或者右孩子的path。此种情况下，这个局域max path sum可以与父节点的root.val叠加产生更长的path。

   所以，globalMax = max(case1, case2)

通过以上分析，我们发现，能够有‘递’和‘归’步骤的，是case2. 通过case2，我们也可以求出case1。所以，我们的递归公式，可以基于case2，返回可以为上一层使用的max path sum。同时，我们需要一个全局变量，来记录所有的globalMax.

代码

class Solution(object):    def maxPathSum(self, root):        """        :type root: TreeNode        :rtype: int        """              self.globalMax = float('-inf')        def getLocalMax(root):            if root is None:                return 0            leftMax = getGlobalMax(root.left)            rightMax = getGlobalMax(root.right)            self.globalMax = max(self.globalMax, leftMax + root.val+ rightMax)            return max(0, max(leftMax, rightMax) + root.val)                getLocalMax(root)        return self.globalMax