1. question: 打家劫舍III（中等）
小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。
除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。
给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/house-robber-iii
示例 1:
1
2
3
| 输入: root = [3,2,3,null,3,null,1]
输出: 7
解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7
|
示例 2:
1
2
3
| 输入: root = [3,4,5,1,3,null,1]
输出: 9
解释: 小偷一晚能够盗取的最高金额 4 + 5 = 9
|
提示：
1
2
| 树的节点数在 [1, 104] 范围内
0 <= Node.val <= 104
|
2. answers
这道题最开始没想出来，认为和前面的监控二叉树类似，不过这道题是真难，一点都不会。原始思路如下所示：
1
2
3
4
5
6
7
8
9
10
11
| * TODO 似乎应该比较如果叶子节点之和大于根节点，那么就选取叶子节点。反之，则选取根节点。
* 【注意，此时，这是某棵子树，那么对应的另一棵子树其实也就有了限制】
* 比如，如果一棵树（只有左右节点）：
* 1. 假如选了左节点，那么显然根节点就不能选了。此时，因为不存在负数，此时一定会选右节点。
* 2. 假如没选左节点，即根节点大于左右节点之和，那么就选根节点。
* 那么如果一棵树（有左右子树）：
* 1. 假如选择了左子树的根节点，此时对右子树是没要求的，因为树的根节点肯定是不能选的。右子树只需按照上面选最大值即可。
* 2. 加入没有选择左子树的根节点【注意，此时本树的根节点是可选的】；那么右子树，就不能简单按照上面规则了，因为右子树的选择
* 也决定了根节点是否选择。（此时需要比较：右子树根节点 和 右子树孩子节点+根节点 二者）
* 3. 其实对比12，这两种情况完全可以对调。也就是说，似乎不能按照左右节点之和和根节点之间的大小来比较。
* 难道是直接逐层来比较吗？似乎也不是。因为上述情况2
|
参考了题解。首先是递归法。利用树的递归性质。当前根节点，只有选和不选两种状态，选的话，子节点肯定不选【直接递归节点的子节点】；而不选的话，子节点可选可不选【即递归到自身】。最终比较节点的两种取值即可。
因此可先序遍历（递归），如果节点为空，则返回0，如果左右节点为null，则返回自身值。代码如下所示：
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| public class Solution_0131 {
public int rob(TreeNode root) {
if(root == null) return 0;
if(root.left == null && root.right == null) return root.val;
int selThis = root.val;
if(root.left != null) selThis += rob(root.left.left) + rob(root.left.right);
if(root.right != null) selThis += rob(root.right.left) + rob(root.right.right);
int selNot = 0;
if(root.left != null) selNot += rob(root.left);
if(root.right != null) selNot += rob(root.right);
return Math.max(selThis, selNot);
}
public static void main(String[] args) {
System.out.println();
TreeNode tn6 = new TreeNode(1);
TreeNode tn5 = new TreeNode(3);
TreeNode tn4 = new TreeNode(1);
TreeNode tn3 = new TreeNode(5, null, tn6);
TreeNode tn2 = new TreeNode(4, tn4, tn5);
TreeNode tn1 = new TreeNode(3, tn2, tn3);
Solution_0131 s = new Solution_0131();
System.out.println(s.rob(tn1));
}
}
|
但是，上面递归存在着重复计算。
对于二叉树【A，B，C，D，E，G，F】，显然当A不选的时候，需要递归BC。当B不选的时候，需要递归DE，返回自身值；当B选的时候，需要递归DE的子节点，返回0。对于C同样如此。但是当A选的时候，需要递归DE，此时和上面重复。
因此，可存储节点的遍历结果，来进行优化。
设置Map<TreeNode, Integer>保存该节点作为根节点的二叉树，【选、不选】的最优情况。之后，后续再需要遍历递归该节点的时候，直接取即可。代码如下所示：
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
| public class Solution_0131_02 {
public Map<TreeNode, Integer> map = new HashMap<>();
public int rob(TreeNode root) {
if(root == null) return 0;
if(root.left == null && root.right == null) return root.val;
if(map.containsKey(root)) return map.get(root);
int selThis = root.val;
if(root.left != null) selThis += rob(root.left.left) + rob(root.left.right);
if(root.right != null) selThis += rob(root.right.left) + rob(root.right.right);
int selNot = 0;
if(root.left != null) selNot += rob(root.left);
if(root.right != null) selNot += rob(root.right);
map.put(root, Math.max(selThis, selNot));
return Math.max(selThis, selNot);
}
public static void main(String[] args) {
System.out.println();
TreeNode tn5 = new TreeNode(1);
TreeNode tn4 = new TreeNode(3);
TreeNode tn3 = new TreeNode(3, null, tn5);
TreeNode tn2 = new TreeNode(2, null, tn4);
TreeNode tn1 = new TreeNode(3, tn2, tn3);
Solution_0131_02 s = new Solution_0131_02();
System.out.println(s.rob(tn1));
}
}
|
除了递归，可采用动态规划，一个节点的取值只有选和不选两种情况，经过前面分析，其实以当前节点为根节点的二叉树，所能取得的最大值有两种情况：【根节点不选，左右子树各自的最大值（选、不选取最大）之和】、【根节点选 + 左右子树根节点不选的值之和】。
而左右子树同样是这种情况，经过递归，最终到达叶子节点。
显然叶子节点只有选和不选两种取值。因此，设置数组保存【选，不选】两种值，逐步向上递推即可。一个需要注意的点就是，当本节点不选的时候，左子树的最大值是其选不选的最大值，右子树同理；而当本节点选的时候，一定是左右子树都不选的值（而无需管选的值如何）。
代码如下所示：
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| public class Solution_0131_03 {
public int[] robTree(TreeNode root) {
if(root == null) return new int[]{0, 0};
if(root.left == null && root.right == null) return new int[]{0, root.val};
int[] nodeThis = new int[2];
int[] left = robTree(root.left);
int[] right = robTree(root.right);
nodeThis[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
nodeThis[1] = left[0] + right[0] + root.val;
return nodeThis;
}
public int rob(TreeNode root) {
int[] result = robTree(root);
return Math.max(result[0], result[1]);
}
public static void main(String[] args) {
System.out.println();
TreeNode tn5 = new TreeNode(1);
TreeNode tn4 = new TreeNode(3);
TreeNode tn3 = new TreeNode(3, null, tn5);
TreeNode tn2 = new TreeNode(2, null, tn4);
TreeNode tn1 = new TreeNode(3, tn2, tn3);
Solution_0131_03 s = new Solution_0131_03();
System.out.println(s.rob(tn1));
}
}
|
3. 备注
参考力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)，代码随想录 (programmercarl.com)。
