二叉树中的最大路径和

• 第一种：左子树的最大路径和
• 第二种：右子树的最大路径和
  *第三种：包含root节点的路径和
  LeetCode题目地址

def getMaxPathSum(self, root):
        if root == None:
            return -sys.maxint,0
        
        leftMax, leftRootMax = self.getMaxPathSum(root.left)
        rightMax, rightRootMax = self.getMaxPathSum(root.right)
        #计算最大值
        pathMax = max(leftMax, rightMax, leftRootMax + rightRootMax + root.val)
        rootMax = max(rightRootMax + root.val, leftRootMax + root.val,0)
        
        return pathMax, rootMax
    def maxPathSum(self, root):
        # write your code here
        maxsum,_ = self.getMaxPathSum(root)
        return maxsum