LeetCode_131_HouseRobberIII


1. question: 打家劫舍III(中等)

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口,我们称之为 root 。

除了 root 之外,每栋房子有且只有一个“父“房子与之相连。一番侦察之后,聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ,房屋将自动报警。

给定二叉树的 root 。返回 在不触动警报的情况下 ,小偷能够盗取的最高金额 。

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/house-robber-iii

示例 1:

示例1

1
2
3
输入: root = [3,2,3,null,3,null,1]
输出: 7
解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7

示例 2:

示例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 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);

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中。
// 即以本节点为根节点的二叉树已经遍历完成。后续本节点的所有父节点就无需再次遍历了。
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);

// 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_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};

// 0表示本节点不选,1表示选
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);

// 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_03 s = new Solution_0131_03();

System.out.println(s.rob(tn1));
}
}

3. 备注

参考力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)代码随想录 (programmercarl.com)


文章作者: 浮云
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 浮云 !
  目录