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 次阅读