leetcode 337.打家劫舍 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.
递归
【打家劫舍 I】和【打家劫舍 II】都是基于数组的。
而这道题是基于二叉树的。
我们把房子按照二叉树的结构排列好,然后按层横切一刀并记录下每层的编号
仔细看题目中的这句话:如果两个直接相连的房子在同一天晚上被打劫,房屋将自动报警。能直接相连的只有父子节点,兄弟节点是不相连的。
所以这句话的意思是偷了父节点,那么子节点就不能偷了,但还可以继续偷孙子节点。即偷了
第 i
层,那么第i-1
层i+1
层就不能偷了。
比如我偷第2层,也就是上图中2
和3
两个节点。那么第1层的1
和第3层的4
、5
、6
、7
都不能偷了。
注意,这道题跟【打家劫舍 I】、【打家劫舍 II】一样,不能简单的值判断奇偶下标,奇偶层数,比如下图这样就不是按照奇偶层数来的
如何用递归去实现呢?
我们先从根节点分析,对于根节点来说,只有两种选择,偷或者不偷
根节点的这两个选择,会导致它的两个孩子出现三种选择:
1、父节点(也就是根节点)选择偷,那么两个孩子2
和3
也就只能选不偷
2、父节点选择不偷,两个孩子可以选择偷
3、父节点选择不偷,两个孩子依然可以选择不偷
对于根节点的左孩子2
的两种选择也会导致它的孩子4
和5
出现三种状态
1、2
选择偷,4
和5
只能选择不偷
2、2
选择不偷,4
和5
可以选择偷
3、2
选择不偷,4
和5
也可以选择不偷
根节点的右孩子3
也是一样的
1、3
选择偷,6
和7
只能选择不偷
2、3
选择不偷,6
和7
可以选择偷
3、3
选择不偷,6
和7
也可以选择不偷
根节点的左孩子的左孩子4
依然是这样
所以,对于任意节点来说,有三种状态
1、如果父节点选择偷,那么本节点只能选择不偷
2、如果父节点选择不偷,那么本节点可以选择偷
3、如果父节点选择不偷,那么本节点依旧可以选择不偷
那么递归逻辑就可以这么实现:
if(父节点选择偷):
a = 获取左孩子的最大值(本节点不偷) + 获取右孩子的最大值(本节点不偷)
else(父节点选择不偷):
b = 获取左孩子的最大值(本节点偷) + 获取右孩子的最大值(本节点偷) + 本节点的值
c = 获取左孩子的最大值(本节点不偷) + 获取右孩子的最大值(本节点不偷)
返回 max(a,b,c)
父节点选择偷/不偷,可以作为状态参传入即可。
这里我们还可以把c
单独领出来,不放到if-else里面,即表示什么也不干
java代码:
class Solution { public int rob(TreeNode root) { if(root==null) { return 0; } return dfs(root,0); } private int dfs(TreeNode root,int status) { if(root==null) { return 0; } int a=0,b=0,c=0; //不管父节点选择偷/不偷,本次什么都不干 a = dfs(root.left,status)+dfs(root.right,status); //父节点选择偷,本次不偷 if(status==1) { b = dfs(root.left,0)+dfs(root.right,0); } //父节点选择不偷,本次选择偷 else { c = dfs(root.left,1)+dfs(root.right,1)+root.val; } //返回三种状态的最大值 return Math.max(a,Math.max(b,c)); } }
python代码:
class Solution(object): def rob(self, root): if not root: return 0 def dfs(root,status): if not root: return 0 a,b,c = 0,0,0 # 不管父节点选择偷/不偷,本次什么都不干 a = dfs(root.left,status)+dfs(root.right,status) # 父节点选择偷,本次不偷 if status: b = dfs(root.left,0)+dfs(root.right,0) # 父节点选择不偷,本次选择偷 else: c = dfs(root.left,1)+dfs(root.right,1)+root.val # 返回三种状态的最大值 return max(a,b,c) return dfs(root,0)
递归+记忆化
这里的记忆化跟一维数组不同,一维数组的递归+记忆化,从调用上来说,就是去掉重复的分支调用(剪枝)。
而在一颗二叉树上再做递归,就不是剪枝,而是减少某个节点的反复调用次数。
以上图10
这个节点为例
从1->2->5->10 这个调用关系来看,每个节点都会经历偷/不偷这样的状态
而由此会引发10
这个节点被反复调用很多次
假设根节点1
要计算偷这个状态下的最大值,此时10
这个节点会被反复第调用好几次
再假设根节点1
要计算不偷这个状态下的最大值,此时10
这个节点仍旧会被反复调用很多次
对于10
这个节点来说,只需要计算偷和不偷两种状态下的最大值即可,剩下的那些都是重复的调用,所以可以用缓存记录下这两种状态的最大值,这样就可以省掉大量的重复计算。
java代码:
class Solution { public int rob(TreeNode root) { if(root==null) { return 0; } //缓存的key是TreeNode和状态的组合,这里将TreeNode和status封装成一个Pair对象作为key Map<Pair,Integer> cache = new HashMap<Pair,Integer>(); return dfs(cache,root,0); } private int dfs(Map<Pair,Integer> cache,TreeNode root,int status) { if(root==null) { return 0; } //创建一个Pair对象作为key,key的内容是TreeNode和status组合 Pair p = new Pair(root,status); if(cache.containsKey(p)) { return cache.get(p); } //后面的逻辑跟递归版本是一样的 int a=0,b=0,c=0; a = dfs(cache,root.left,status)+dfs(cache,root.right,status); if(status==1) { b = dfs(cache,root.left,0)+dfs(cache,root.right,0); } else { c = dfs(cache,root.left,1)+dfs(cache,root.right,1)+root.val; } //将Pair和最大值缓存起来 cache.put(p,Math.max(a,Math.max(b,c))); return cache.get(p); } //这里自定义一个Pair对象,用来封装TreeNode和status,Pair作为哈希表的key //同时还需要重新定义Pair的hashCode()和equals()两个函数 class Pair { TreeNode root; int status; Pair(TreeNode root,int status) { this.root = root; this.status = status; } public int hashCode() { return root.hashCode()+status; } public boolean equals(Object obj) { if(obj==null) { return false; } Pair p = (Pair)obj; if(p.root.hashCode()==root.hashCode() && p.status==status) { return true; } return false; } } }
python代码:
class Solution(object): def rob(self, root): if not root: return 0 # 创建一个缓存省去重复调用 cache = dict() # 这里的逻辑跟递归版本一样,只是加上了缓存 def dfs(root,status): if not root: return 0 if (root,status) in cache: return cache[root,status] a,b,c = 0,0,0 a = dfs(root.left,status)+dfs(root.right,status) if status: b = dfs(root.left,0)+dfs(root.right,0) else: c = dfs(root.left,1)+dfs(root.right,1)+root.val cache[root,status] = max(a,b,c) return cache[root,status] return dfs(root,0)
动态规划
这道题是树形DP问题
递归解法中中我们是自顶向下的方式求解的,而动态规划中我们采用自底向上的方式。
假设要求下图中橙色1
这个节点最大值,我们可以这么做
1、求出橙色1
的四个孙子节点最大值的累加,再加上橙色节点1
本身的值,记做a
2、求出橙色1
的两个孩子节点的最大值的累加,记做b
那么橙色节点1
的最大值就是max(a,b)
但是光求出这个值还是少点了,为什么呢?
假设橙色节点还有一个父节点,也就是下图中的绿色节点
绿色节点的最大值
1、橙色节点1
的两个孩子节点最大值累加,再加上节点a
的两个孩子最大值累加,加上绿色节点本身,将这个值记做x
2、橙色节点1
的最大值,加上节点a
的最大值,记做y
绿色节点的最大值就是max(x,y)
所以对于任意节点来说,我们需要返回两个值
一个值是当前节点本身的最大值a
,对应的是上图中第i层的4
另一个是孩子节点累加后的最大值b
,对应的是第i+1层4
的两个孩子
因为计算第i-1层的某个节点时,需要用到 第i层 和 第i+1层 的值
第i层4
的返回值会被第i-1层的5
和第i-2层的2
用到
整个计算过程如下,下图中的执行过程和代码中真实的执行逻辑有些差别,我做了一些简化,但所表达的求解思路是类似的
java代码:
class Solution { public int rob(TreeNode root) { if(root==null) { return 0; } Pair p = dfs(root); return Math.max(p.v1,p.v2); } private Pair dfs(TreeNode root) { //如果节点为空就返回(0,0)第一个0表示当前节点的最大值,第二个0表示所有子节点的最大值 if(root==null) { return new Pair(0,0); } //获取左右节点的值,这里会拿到四个值,左节点的值,左节点孩子的值,右节点的值,右节点孩子的值 //pleft.v1,pleft.v2,pright.v1,pright.v2 Pair pleft = dfs(root.left); Pair pright = dfs(root.right); //pleft.v2表示left的所有所有子节点,a就是当前节点的值+孙子节点的值 int a = pleft.v2+pright.v2+root.val; //b就是两个孩子节点的值 int b = pleft.v1+pright.v1; //当前节点的最大值就是max(a,b),同时还要返回子节点的最大值,因为当前节点的父节点会用到 Pair res = new Pair(Math.max(a,b),b); return res; } //自定义的Pair对象,封装了两个整数作为返回值 class Pair { //v1表示当前节点的最大值,v2表示所有子节点的最大值 int v1; int v2; Pair(int v1,int v2) { this.v1 = v1; this.v2 = v2; } } }
python代码:
class Solution(object): def rob(self, root): if not root: return 0 def dfs(root): # 如果节点为空就返回(0,0)第一个0表示当前节点的最大值,第二个0表示所有子节点的最大值 if not root: return 0,0 # 获取左右节点的值,这里会拿到四个值,左节点的值,左节点孩子的值,右节点的值,右节点孩子的值 left,left_pre = dfs(root.left) right,right_pre = dfs(root.right) # a就是当前节点的值+孙子节点的值 a = left_pre+right_pre+root.val # b就是两个孩子节点的值 b = left+right # 当前节点的最大值就是max(a,b),同时还要返回子节点的最大值,因为当前节点的父节点会用到 return max(a,b),b a,b = dfs(root) return max(a,b)
3 次阅读