Skip to content

Instantly share code, notes, and snippets.

@gudnm
Last active April 8, 2018 02:28
Show Gist options
  • Save gudnm/f4520dfd0988fe5bdb30b0ffcf071864 to your computer and use it in GitHub Desktop.
Save gudnm/f4520dfd0988fe5bdb30b0ffcf071864 to your computer and use it in GitHub Desktop.
# Definition for a binary tree node
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
# @param A : root node of tree
# @return an integer
def __init__(self):
self.maxsum = -2**31
def dfs(self, node):
if not node.left and not node.right:
self.maxsum = max(self.maxsum, node.val)
return node.val
else:
if node.left and node.right:
tleft = self.dfs(node.left)
tright = self.dfs(node.right)
self.maxsum = max(self.maxsum, node.val, node.val+tleft+tright)
return max(tleft, tright)+node.val
elif node.left:
tleft = self.dfs(node.left)
self.maxsum = max(self.maxsum, node.val, node.val+tleft)
return node.val+tleft
else:
tright = self.dfs(node.right)
self.maxsum = max(self.maxsum, node.val, node.val+tright)
return node.val+tright
def maxPathSum(self, A):
self.dfs(A)
return self.maxsum
if __name__ == '__main__':
t = TreeNode(-1)
t.left = TreeNode(-2)
t.left.left = TreeNode(-3)
t.left.right = TreeNode(-4)
t.left.right.left = TreeNode(-5)
s = Solution()
assert s.maxPathSum(t) == -1
t = TreeNode(1)
t.left = TreeNode(2)
t.left.left = TreeNode(3)
t.left.right = TreeNode(4)
t.left.right.left = TreeNode(5)
s = Solution()
assert s.maxPathSum(t) == 14
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment