0%

leetcode: house robber III

一、题目要求

所有房子排列成一个二叉树的结构。

如果两个直接相连的房子在同一天晚上被打劫,房屋将自动报警。

计算在不触动警报的情况下,小偷一晚能够盗取的最高金额。

二、分析

用递归比较选择和不选择当前节点的最大收益,并把结果缓存起来。

三、实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
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