共计 2948 个字符，预计需要花费 8 分钟才能阅读完成。
337. 打家劫舍 III
题目起源：力扣（LeetCode）https://leetcode-cn.com/problems/house-robber-iii
题目
在上次打劫完一条街道之后和一圈屋宇后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，咱们称之为“根”。除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪慧的小偷意识到“这个中央的所有屋宇的排列相似于一棵二叉树”。如果两个间接相连的房子在同一天早晨被打劫，屋宇将主动报警。
计算在不触动警报的状况下，小偷一晚可能盗取的最高金额。
示例 1:
输出: [3,2,3,null,3,null,1]
3
/ \
2 3
\ \
3 1
输入: 7
解释: 小偷一晚可能盗取的最高金额 = 3 + 3 + 1 = 7.示例 2:
输出: [3,4,5,1,3,null,1]
3
/ \
4 5
/ \ \
1 3 1
输入: 9
解释: 小偷一晚可能盗取的最高金额 = 4 + 5 = 9.解题思路
这道题是【198. 打家劫舍】、【213. 打家劫舍 II】的后续
思路：递归、动静布局
在这道题当中，偷窃的对象不再是一条街或者围成圈的屋宇。而是看似二叉树排布的屋宇。在这里，咱们会用动静布局的办法来解决。
不过在此之前，咱们先看题目，【如果两个间接相连的房子在同一天早晨被打劫，屋宇将主动报警】，这里的意思是，不可能偷窃相连的两个节点，也就是不能同时偷窃属于父子关系的节点。
题目给定的二叉树中，节点上的权值也就是要偷窃的金额，依照下面的条件，也就是说，每个节点都有两种状态：已偷取、未偷取。因为不能同时偷窃属于父子关系的节点，求该条件限定下，能偷取的金额最大值为多少。
递归
在这里，咱们先用递归的办法来解决，这里依据下面的剖析，分状况来探讨，具体思路如下（基于三层的二叉树形容）：
- 当偷窃根节点时，则无奈偷窃根节点下的左右子节点，然而能够抉择投左右子节点下的子树。
- 当不偷窃根节点时，则能够思考偷窃根节点下的左右子节点。
那么，大抵的代码如下：
# 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
# 分状况
# 偷窃根节点 与 不偷窃根节点
in_root = root.val
if root.left:
# 偷窃根节点时，无奈偷取子节点，那么偷窃子孙节点
in_root += self.rob(root.left.left) +self. rob(root.left.right)
if root.right:
in_root += self.rob(root.right.left) +self. rob(root.right.right)
# 不偷取根节点，那么收益就是左右子节点权值的总和
not_in_root = self.rob(root.left) + self.rob(root.right)
# 返回大值
return max(in_root, not_in_root)下面这段代码执行后超时，因为在计算子孙节点的时候，计算了根节点下的左右子树，而后续计算又反复计算了子孙节点。在这里，咱们来进行优化，将计算后的后果存储到哈希表中，遇到须要反复计算的局部，间接拿过去，不须要再次递归计算。
优化后代码见【代码实现 # 递归（优化）】
动静布局
从下面递归的办法中，咱们能够发现，最终最大收益为 in_root 和 not_in_root 的最大值。
也就是说，每个子树都有最优解：偷窃根节点 和 不偷窃根节点下的最优解。
咱们从新定义这个问题，每个节点能够抉择偷或者不偷，那么相连节点不能一起偷，那么：
- 如果以后节点抉择偷窃时，左右子节点不抉择偷；
- 如果以后节点抉择不偷时，左右子节点次要能取得最优解就行。
定义数组存储两个状态，索引 0 示意不偷，索引 1 示意偷。那么每个节点能偷到最大金额可定义为：
- 以后节点抉择偷窃时，最大金额数 = 左子节点不偷能取得的最大金额 + 右子节点不偷能取得的最大金额 + 以后节点的金额
- 以后节点抉择不偷时，最大金额 = 左子节点能偷的最大金额 + 右子节点能偷的最大金额。
那么相应的转移公式为：
# 以后节点不偷
ans[0] = max(rob(root.left)[0], rob(root.left)[1])
+ max(rob(root.right)[0], rob(root.right)[1])
# 以后节点抉择偷
ans[1] = rob(root.left)[0] + rob(root.right)[0] + root.val具体代码见【代码实现 # 动静布局】
代码实现
# 递归（优化）# 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:
# 存储计算过的后果
hash_map = {}
def helper(root):
if not root:
return 0
# 如果存在于哈希表中，间接拿过去用
if root in hash_map:
return hash_map[root]
in_root = root.val
if root.left:
# 偷窃根节点时，无奈偷取子节点，那么偷窃子孙节点
in_root += helper(root.left.left) +helper(root.left.right)
if root.right:
in_root += helper(root.right.left) +helper(root.right.right)
# 不偷取根节点，那么收益就是左右子节点权值的总和
not_in_root = helper(root.left) + helper(root.right)
ans = max(in_root, not_in_root)
# 这里计算完之后，将后果存入哈希表中
hash_map[root] = ans
return ans
return helper(root)
# 动静布局
# 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:
def helper(root):
if not root:
return [0, 0]
ans = [0, 0]
left = helper(root.left)
right = helper(root.right)
# 两个索引对应两种状态，索引 0 示意不偷，索引 1 示意偷
ans[0] = max(left[0], left[1]) + max(right[0], right[1])
ans[1] = left[0] + right[0] + root.val
return ans
ans = helper(root)
return max(ans[0], ans[1])实现后果
欢送关注
公众号【书所集录】
