FilesExpand file tree

master

/

rob.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

30 lines (28 loc) · 1.03 KB

master

/

rob.py

Copy path

Top

File metadata and controls

• Code
• Blame

30 lines (28 loc) · 1.03 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

"""

Answe inspired by the post from here:

https://leetcode.com/problems/house-robber-iii/discuss/79330/Step-by-step-tackling-of-the-problem

"""

# Method 1: dynamic programming solution:

def rob1(self, root):

lookup = {}

def helper(root):

if not root: return 0

if root in lookup: return lookup[root]

val = 0

if root.left:

val += helper(root.left.left) + helper(root.left.right)

if root.right:

val += helper(root.right.left) + helper(root.right.right)

val = max(val + root.val, helper(root.left) + helper(root.right))

lookup[root] = val

return val

return helper(root)

# Method 2: Greedy approach:

def rob2(self, root):

def helper(root):

if not root: return [0, 0]

left, right = helper(root.left), helper(root.right)

not_robbed = max(left) + max(right)

robbed = root.val + left[0] + right[0]

return [not_robbed, robbed]

return max(helper(root))