一、题目描述
小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。
除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。
给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。
二、解题思路
求“盗取最高金额”，所以考虑用动态规划。该题涉及在二叉树中利用动态规划求取最优子结构。考虑到每个节点有1）选择 2）不选择两种情况，且当前节点的选择与不选择会影响其子节点的选择情况，所以考虑利用二叉树的后序遍历，先考虑子节点的情况，再考虑父节点。
三、代码实现
xxxxx（1）一开始的错误思路！！！
// 思路有错误：我的思路认为当可以选择某行中元素时，该行所有元素都应该被选中，这显然是错误的
// 比如我选左孩子不选右孩子，那么下一次我就可以不选左孩子的所有孩子，但可以选右孩子的所有孩子
public int rob1(TreeNode root) {
//首先层序遍历，每层之和存入数组
List<Integer> sumPerLevel = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
int sum = 0;
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
sum += node.val;
}
System.out.println(sum + " ");
sumPerLevel.add(sum);
}
//进行动态规划
int len = sumPerLevel.size();
int[][] dp = new int[len][3];
//初始化[0][0]表示选
dp[0][0] = sumPerLevel.get(0);
dp[0][1] = 0;
dp[0][2] = 0;
for (int i = 1; i < len; i++) {
dp[i][0] = Math.max(dp[i - 1][1], dp[i - 1][2]) + sumPerLevel.get(i);
dp[i][1] = dp[i - 1][0];
dp[i - 1][2] = Math.max(dp[i - 1][1], dp[i - 1][2]);
}
return Math.max(dp[len - 1][0], Math.max(dp[len - 1][1], dp[len - 1][2]));
}
正确解法如下：?
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
// 存储选择当前元素时，该节点对应最大值
Map<TreeNode, Integer> f = new HashMap<>();
// 存储不选择当前元素时，该节点对应最大值
Map<TreeNode, Integer> g = new HashMap<>();
//---------------------------分割线-------------------
public int rob(TreeNode root) {
dfs(root);
return Math.max(f.getOrDefault(root, 0), g.getOrDefault(root, 0));
}
public void dfs(TreeNode root) {
if (root == null) {
return;
}
//后序遍历
dfs(root.left);
dfs(root.right);
// 当前父节点选，则子节点必定不选
f.put(root, g.getOrDefault(root.left, 0) + g.getOrDefault(root.right, 0) + root.val);
// 当前父节点不选，则节点可能选可能不选
g.put(root, Math.max(f.getOrDefault(root.left, 0), g.getOrDefault(root.left, 0)) + Math.max(f.getOrDefault(root.right, 0), g.getOrDefault(root.right, 0)));
}
}
