The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the “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 forms a binary tree”. It will automatically contact the police if two directly-linked houses were broken into on the same night.
Determine the maximum amount of money the thief can rob tonight without alerting the police.
Example 1:
Input: [3,2,3,null,3,null,1]
3
/ \
2 3
\ \
3 1
Output: 7
Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.
Example 2:
Input: [3,4,5,1,3,null,1]
3
/ \
4 5
/ \ \
1 3 1
Output: 9
Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.
Solutions
1. 递归
使用 DFS 图搜索，注意记忆化！
# Time Complexity: O(n^2)
# Space Complexity: O(n)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def rob(self, root: TreeNode) -> int:
if not root:
return 0
if root.left:
ll = self.rob(root.left.left)
lr = self.rob(root.left.right)
else:
ll, lr = 0, 0
if root.right:
rl = self.rob(root.right.left)
rr = self.rob(root.right.right)
else:
rl, rr = 0, 0
return max(root.val + ll + lr + rl + rr, self.rob(root.left) + self.rob(root.right))
报超时了，忧伤。
2. 递归+记忆化
加一个记忆化，不需要重复计算。
# Time Complexity: O(n)
# Space Complexity: O(n)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def __init__(self):
self.memo = collections.defaultdict()
def rob(self, root: TreeNode) -> int:
if not root:
return 0
if root in self.memo:
return self.memo[root]
if root.left:
ll = self.rob(root.left.left)
lr = self.rob(root.left.right)
else:
ll, lr = 0, 0
if root.right:
rl = self.rob(root.right.left)
rr = self.rob(root.right.right)
else:
rl, rr = 0, 0
self.memo[root] = max(root.val + ll + lr + rl + rr, self.rob(root.left) + self.rob(root.right))
return self.memo[root]
# Runtime: 48 ms, faster than 96.90% of Python3 online submissions for House Robber III.
# Memory Usage: 15.3 MB, less than 80.00% of Python3 online submissions for House Robber III.
3. DFS-递归-抢或不抢
# Time Complexity: O(n)
# Space Complexity: O(n)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def rob(self, root: TreeNode) -> int:
rob_val, not_rob_val = self.rob_or_not_rob(root)
return max(rob_val, not_rob_val)
def rob_or_not_rob(self, root: TreeNode):
if not root:
return 0, 0
left_rob, left_not_rob = self.rob_or_not_rob(root.left)
right_rob, right_not_rob = self.rob_or_not_rob(root.right)
# rob this root node, the left and right childs are not rob
rob_val = root.val + left_not_rob + right_not_rob
# if not rob this root node, so the thief can choose rob or not in both the left and right childs
not_rob_val = max(left_rob, left_not_rob) + max(right_rob, right_not_rob)
return rob_val, not_rob_val
# Runtime: 44 ms, faster than 99.07% of Python3 online submissions for House Robber III.
# Memory Usage: 14.6 MB, less than 100.00% of Python3 online submissions for House Robber III.