# coding: utf-8 class Solution: """ @param root: The root of binary tree. @return: An integer """ def maxPathSum(self, root): # write your code here if not root: return 0 self.ret = -2147483648 self._maxPathSum(root) return self.ret def _maxPathSum(self, root): if not root: return 0 left_sum = self._maxPathSum(root.left) right_sum = self._maxPathSum(root.right) ''' 从以下值中比较获取最大值与self.ret比较并更新 - root.val - root.val + max_left_sum - root.val + max_right_sum - root.val + max_left_sum + max_right_sum 这个值是当前包含该节点的最大路径和 ''' sub_max = max(root.val + left_sum, root.val + right_sum) sub_max = max(sub_max, root.val) sub_max = max(sub_max, root.val + left_sum + right_sum) if sub_max > self.ret: self.ret = sub_max ''' 返回值应当是以下值中比较获取最大，因为路径要向上延伸： - root.val - root.val + max_left_sum - root.val + max_right_sum ''' return max(max(root.val + left_sum, root.val + right_sum), root.val) # medium: http://lintcode.com/zh-cn/problem/binary-tree-maximum-path-sum/