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)。