LeetCode|LeetCode 337. 打家劫舍 III | Python LeetCode337.打家劫舍III|Python

337. 打家劫舍 III 题目来源：力扣（LeetCode）https://leetcode-cn.com/problems/house-robber-iii
题目在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。
计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。
示例 1:

输入: [3,2,3,null,3,null,1]3 / \ 23 \\ 31输出: 7 解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.

示例 2:

输入: [3,4,5,1,3,null,1]3 / \ 45 / \\ 131输出: 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 = Noneclass 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 的最大值。
也就是说，每个子树都有最优解：偷窃根节点和不偷窃根节点下的最优解。
我们重新定义这个问题，每个节点可以选择偷或者不偷，那么相连节点不能一起偷，那么：

如果当前节点选择偷窃时，左右子节点不选择偷；
如果当前节点选择不偷时，左右子节点主要能获得最优解就行。

【LeetCode|LeetCode 337. 打家劫舍 III | Python】定义数组存储两个状态，索引 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 = Noneclass 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 = Noneclass 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.valreturn ansans = helper(root) return max(ans[0], ans[1])

实现结果