【题目描述】
小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列
输入: root = [3,2,3,null,3,null,1]
输出: 7
解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7
【解题代码】
package dp;
import common.Utils;
import tree.binarytree.TreeNode;
import java.util.*;
public class Rob3 {
// 中间结果缓存map
private Map<Integer, Integer> intResultCache = new HashMap<>();
public static void main(String[] args) {
//Integer[] array = new Integer[]{3, 2, 3, null, 3, null, 1};
//Integer[] array = new Integer[]{3, 4, 5, 1, 3, null, 1};
//Integer[] array = new Integer[]{4, 1, null, 2, null, 3};
//Integer[] array = new Integer[]{2, 1, 3, null, 4};
Integer[] array = Utils.readIntegersFromFile("res\\337\\122.txt");
TreeNode root = TreeNode.constructTree(array);
long start = System.currentTimeMillis();
System.out.println("开始计算。。。");
int result = new Rob3().rob(root);
System.out.println("运行时长：" + (System.currentTimeMillis() - start) + "ms");
System.out.println("The result is: " + result);
}
public int rob(TreeNode root) {
// 从根节点开始进行计算，根节点没有父节点，所以是否抢劫为false
return rob(root, false);
}
private int rob(TreeNode node, boolean parent) {
// 节点为空，返回0
if (node == null) {
return 0;
}
// 获取当前节点hashcode，如果父节点被抢劫，hashcode加1
int hashCode = node.hashCode() + (parent == true ? 1 : 0);
int result = intResultCache.getOrDefault(hashCode, 0);
// 如果缓存不包含当前节点
if (!intResultCache.containsKey(hashCode)) {
// 如果当前节点父节点被抢劫，那么当前节点不能被抢劫，只能计算两个子节点之和
if (parent) {
result = rob(node.left, false) + rob(node.right, false);
} else { // 如果当前节点父节点不被抢劫，那么当前节点可以选择抢劫或不抢劫
// 当前节点被抢劫, 当前节点抢劫最大金额等于本节点现金加上两个子节点之和
int result1 = node.val + rob(node.left, true) + rob(node.right, true);
// 当前节点不被抢劫, 当前节点抢劫最大金额等于两个子节点之和
int result2 = rob(node.left, false) + rob(node.right, false);
// 取两种情况最大值
result = Math.max(result1, result2);
}
// 将计算结果缓存起来
intResultCache.put(hashCode, result);
}
return result;
}
}
【解题思路】
这一道题又是 LeetCode198题LeetCode-198题：打家劫舍（原创）-CSDN博客和 LeetCode213题LeetCode-213题：打家劫舍II（原创）-CSDN博客的变种，和之前的题目很类似，但数据结构从数组变成了树节点，总结出以下几个要点：
- 如果当前节点父节点被抢劫，那么当前节点不能被抢劫，当前节点抢劫的最大金额等于两个抢劫子节点的最大金额之和；
- 如果当前节点父节点不被抢劫，那么当前节点可以选择抢劫或不抢劫：
- 如果选择不抢劫当前节点，当前节点抢劫的最大金额等于两个抢劫子节点的最大金额之和；
- 如果选择抢劫当前节点，当前节点抢劫的最大金额等于当前节点金额加上两个抢劫子节点的最大金额之和；
- 返回3,4点最大值即可
- 数据结构从数组变成了树节点，选择使用递归来实现此算法
按照上述思路很快写出如下代码：
class Solution {
public int rob(TreeNode root) {
// 从根节点开始进行计算，根节点没有父节点，所以是否抢劫为false
return rob(root, false);
}
private int rob(TreeNode node, boolean parent) {
// 节点为空，返回0
if (node == null) return 0;
if (parent) {
// 如果当前节点父节点被抢劫，那么当前节点不能被抢劫，只能计算两个子节点之和
return rob(node.left,false) + rob(node.right,false);
} else { // 如果当前节点父节点不被抢劫，那么当前节点可以选择抢劫或不抢劫
// 当前节点被抢劫, 当前节点抢劫最大金额等于本节点现金加上两个子节点之和
int result1 = node.val + rob(node.left,true) + rob(node.right,true);
// 当前节点不被抢劫, 当前节点抢劫最大金额等于两个子节点之和
int result2 = rob(node.left,false) + rob(node.right,false);
// 取两种情况最大值
return Math.max(result1, result2);
}
}
}但LeetCode提交之后，报错超时时间限制
查看代码实现，并仔细考虑，觉得问题应该还是出在递归函数存在大量重复调用的情况，如是考虑设计一个缓存来存储已经计算好的节点，按照以下修改代码，再次提交顺利通过
【解题步骤】
- 给Solution类定义一个中间结果值缓存的map变量
private Map<Integer, Integer> intResultCache = new HashMap<>(); - 定义一个抢劫节点函数，参数为当前节点，以及父节点是否被抢劫
private int rob(TreeNode node, boolean parent) { 获取当前节点hashcode，如果父节点被抢劫，hashcode加1，并从缓存中读取此节点最大金额值
int hashCode = node.hashCode() + (parent == true ? 1 : 0); int result = intResultCache.getOrDefault(hashCode, 0);如果缓存不包含当前节点，计算该节点的抢劫金额最大值,并将结果缓存起来
// 如果缓存不包含当前节点 if (!intResultCache.containsKey(hashCode)) { // 如果当前节点父节点被抢劫，那么当前节点不能被抢劫，只能计算两个子节点之和 if (parent) { result = rob(node.left, false) + rob(node.right, false); } else { // 如果当前节点父节点不被抢劫，那么当前节点可以选择抢劫或不抢劫 // 当前节点被抢劫, 当前节点抢劫最大金额等于本节点现金加上两个子节点之和 int result1 = node.val + rob(node.left, true) + rob(node.right, true); // 当前节点不被抢劫, 当前节点抢劫最大金额等于两个子节点之和 int result2 = rob(node.left, false) + rob(node.right, false); // 取两种情况最大值 result = Math.max(result1, result2); } // 将计算结果缓存起来 intResultCache.put(hashCode, result); }最后返回结果result
【思考总结】
- 对于树节点的动态规划算法，一般只能使用递归的方式进行计算；
- 递归函数存在大量重复调用的情况，可以考虑设计一个缓存来存储已经计算好的节点，这样能大大提高算法性能；
- LeetCode解题之前，一定不要看题解，看了就“破功”了！
