一、题目要求
所有房子排列成一个二叉树的结构。
如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。
计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。
二、分析
用递归比较选择和不选择当前节点的最大收益，并把结果缓存起来。
三、实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
mem = {}
class Solution:
def rob(self, root: TreeNode) -> int:
if root == None:
return 0
if root in mem:
return mem[root]
res = root.val
left_go = self.rob(root.left.left) + self.rob(root.left.right) if root.left else 0
right_go = self.rob(root.right.left) + self.rob(root.right.right) if root.right else 0
left = self.rob(root.left) if root.left else 0
right = self.rob(root.right) if root.right else 0
total = max(res + left_go + right_go, left + right)
mem[root] = total
return total
|