在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。
计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。
示例1 ：
1
2
3
4
5
6
7
8
9
10
| 输入: [3,2,3,null,3,null,1]
3
/ \
2 3
\ \
3 1
输出: 7
解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.
|
示例2：
1
2
3
4
5
6
7
8
9
10
| 输入: [3,4,5,1,3,null,1]
3
/ \
4 5
/ \ \
1 3 1
输出: 9
解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.
|
来源：力扣（LeetCode）
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题解：
本题借鉴官方题解，根据该系列前两题，198. 打家劫舍和213. 打家劫舍 II的进阶版题型，将数组换成了二叉树。根据动态规划的思想，我们肯定要递归遍历这棵树。当我们遍历到该结点时，一共有两种情况，第一种是该结点被偷了，那么该结点的左右孩子结点都不应该再去偷，第二种是该结点没有被偷，那么它的左右孩子可能被偷，也可能没有被偷。我们设置两个HashMap结构存储，用selected表示当前结点被偷，unselected表示当前结点没有被偷，对第一种情况，我们需要将当前结点和当前结点孩子结点没有被偷的情况下的值存入，对第二种情况，我们需要保存的是当前结点左右孩子偷或者不偷后的最大值。通过后序遍历，我们就可以得到根结点的最大收益。
具体代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| class Solution {
Map<TreeNode, Integer> selected = new HashMap<>();
Map<TreeNode, Integer> unselected = new HashMap<>();
public int rob(TreeNode root) {
depthFirstSearch(root);
return Math.max(selected.getOrDefault(root, 0), unselected.getOrDefault(root, 0));
}
public void depthFirstSearch(TreeNode node) {
if (node == null) {
return;
}
depthFirstSearch(node.left);
depthFirstSearch(node.right);
selected.put(node, node.val + unselected.getOrDefault(node.left, 0) + unselected.getOrDefault(node.right, 0));
unselected.put(node, Math.max(selected.getOrDefault(node.left, 0), unselected.getOrDefault(node.left, 0)) + Math.max(selected.getOrDefault(node.right, 0), unselected.getOrDefault(node.right, 0)));
}
}
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
|
