二叉树中的最大路径和

yingl · yingl · commit 3fafc487f9d7 · 2016-07-28T16:16:01.000+08:00
diff --git a/binary_tree_maximum_path_sum.py b/binary_tree_maximum_path_sum.py
@@ -0,0 +1,40 @@
+# -*- 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)
