FilesExpand file tree

 master

/

binary-tree-maximum-path-sum.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

44 lines (41 loc) · 1.06 KB

 master

/

binary-tree-maximum-path-sum.py

Copy path

Top

File metadata and controls

• Code
• Blame

44 lines (41 loc) · 1.06 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

# Time: O(n)

# Space: O(h), h is height of binary tree

#

# Given a binary tree, find the maximum path sum.

#

# The path may start and end at any node in the tree.

#

# For example:

# Given the below binary tree,

#

# 1

# / \

# 2 3

# Return 6.

#

# Definition for a binary tree node

class TreeNode:

def __init__(self, x):

self.val = x

self.left = None

self.right = None

class Solution:

maxSum = float("-inf")

# @param root, a tree node

# @return an integer

def maxPathSum(self, root):

self.maxPathSumRecu(root)

return self.maxSum

def maxPathSumRecu(self, root):

if root is None:

return 0

left = max(0, self.maxPathSumRecu(root.left))

right = max(0, self.maxPathSumRecu(root.right))

self.maxSum = max(self.maxSum, root.val + left + right)

return root.val + max(left, right)

if __name__ == "__main__":

root = TreeNode(1)

root.left = TreeNode(2)

root.right = TreeNode(3)

result = Solution().maxPathSum(root)

print result