- 第一种：左子树的最大路径和
- 第二种：右子树的最大路径和
*第三种：包含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
