-
Notifications
You must be signed in to change notification settings - Fork 42
/
house-robber-iii.py
176 lines (143 loc) · 5.26 KB
/
house-robber-iii.py
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
"""
337. House Robber III
Medium
The thief has found himself a new place for his thievery again. There is only one entrance to this area, called root.
Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that all houses in this place form a binary tree. It will automatically contact the police if two directly-linked houses were broken into on the same night.
Given the root of the binary tree, return the maximum amount of money the thief can rob without alerting the police.
Example 1:
Input: root = [3,2,3,null,3,null,1]
Output: 7
Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.
Example 2:
Input: root = [3,4,5,1,3,null,1]
Output: 9
Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.
Constraints:
The number of nodes in the tree is in the range [1, 104].
0 <= Node.val <= 104
"""
# V0 : dev
# V1
# IDEA : RECURSION
# https://leetcode.com/problems/house-robber-iii/solution/
class Solution:
def rob(self, root: TreeNode) -> int:
def helper(node):
# return [rob this node, not rob this node]
if not node:
return (0, 0)
left = helper(node.left)
right = helper(node.right)
# if we rob this node, we cannot rob its children
rob = node.val + left[1] + right[1]
# else we could choose to either rob its children or not
not_rob = max(left) + max(right)
return [rob, not_rob]
return max(helper(root))
# V1'
# IDEA : RECURSION WITH MEMORY
# https://leetcode.com/problems/house-robber-iii/solution/
class Solution:
def rob(self, root: TreeNode) -> int:
rob_saved = {}
not_rob_saved = {}
def helper(node, parent_robbed):
if not node:
return 0
if parent_robbed:
if node in rob_saved:
return rob_saved[node]
result = helper(node.left, False) + helper(node.right, False)
rob_saved[node] = result
return result
else:
if node in not_rob_saved:
return not_rob_saved[node]
rob = node.val + helper(node.left, True) + helper(node.right, True)
not_rob = helper(node.left, False) + helper(node.right, False)
result = max(rob, not_rob)
not_rob_saved[node] = result
return result
return helper(root, False)
# V1''
# IDEA : DP
# https://leetcode.com/problems/house-robber-iii/solution/
class Solution:
def rob(self, root: TreeNode) -> int:
if not root:
return 0
# reform tree into array-based tree
tree = []
graph = {-1: []}
index = -1
q = [(root, -1)]
while q:
node, parent_index = q.pop(0)
if node:
index += 1
tree.append(node.val)
graph[index] = []
graph[parent_index].append(index)
q.append((node.left, index))
q.append((node.right, index))
# represent the maximum start by node i with robbing i
dp_rob = [0] * (index+1)
# represent the maximum start by node i without robbing i
dp_not_rob = [0] * (index+1)
for i in reversed(range(index+1)):
if not graph[i]: # if is leaf
dp_rob[i] = tree[i]
dp_not_rob[i] = 0
else:
dp_rob[i] = tree[i] + sum(dp_not_rob[child]
for child in graph[i])
dp_not_rob[i] = sum(max(dp_rob[child], dp_not_rob[child])
for child in graph[i])
return max(dp_rob[0], dp_not_rob[0])
# V1''''
# https://blog.csdn.net/fuxuemingzhu/article/details/80779068
# for more solutions, plz check the link above
class Solution(object):
def rob(self, root):
"""
:type root: TreeNode
:rtype: int
"""
def dfs(root):
# from bottom to top
if not root: return [0, 0] # before layer, no robcurr, robcurr
robleft = dfs(root.left)
robright = dfs(root.right)
norobcurr = robleft[1] + robright[1]
robcurr = max(root.val + robleft[0] + robright[0], norobcurr)
return [norobcurr, robcurr]
return dfs(root)[1]
# V1''''''
# https://www.hrwhisper.me/leetcode-house-robber-iii/
class Solution(object):
def rob(self, root):
"""
:type root: TreeNode
:rtype: int
"""
return self.dfs_rob(root)[0]
def dfs_rob(self, root):
if not root: return 0,0
rob_L, no_rob_L = self.dfs_rob(root.left)
rob_R, no_rob_R = self.dfs_rob(root.right)
return max(no_rob_L + no_rob_R + root.val , rob_L + rob_R), rob_L + rob_R
# V2
# Time: O(n)
# Space: O(h)
class Solution(object):
def rob(self, root):
"""
:type root: TreeNode
:rtype: int
"""
def robHelper(root):
if not root:
return (0, 0)
left, right = robHelper(root.left), robHelper(root.right)
return (root.val + left[1] + right[1], max(left) + max(right))
return max(robHelper(root))