-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathBinaryTreeMaximumPathSum.py
More file actions
29 lines (26 loc) · 920 Bytes
/
BinaryTreeMaximumPathSum.py
File metadata and controls
29 lines (26 loc) · 920 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def maxPathSum(self, root):
"""
:type root: TreeNode
:rtype: int
"""
self.maxium = -0x7fffffff
self.maxSubPath(root)
return self.maxium
def maxSubPath(self, root):
if not root: return 0
left = self.maxSubPath(root.left)
right = self.maxSubPath(root.right)
if left > 0 and right > 0:
self.maxium = max(self.maxium, left + right + root.val)
return root.val + max(left,right)
else:
max_sub = max(root.val, max(right,left) + root.val) #if right and left both are < 0, the max sub path is root
self.maxium = max(self.maxium, max_sub)
return max_sub