打家劫舍Ⅲ【LC337】
小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。
除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。
给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/house-robber-iii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
果然是 （线下面试 忙忘了）
DFS【超时】
如果抢了当前节点，两个孩子就不能动，如果没抢当前节点，就可以考虑抢左右孩子,最后取最大值返回
// 有重复计算 // 1.递归去偷，超时 public int rob(TreeNode root) { if (root == null) return 0; int money = root.val; if (root.left != null) { money += rob(root.left.left) + rob(root.left.right); } if (root.right != null) { money += rob(root.right.left) + rob(root.right.right); } return Math.max(money, rob(root.left) + rob(root.right)); }
复杂度
时间复杂度：O(n^2)
空间复杂度：O ( l o g n )
DFS 使用map集合存放计算的结果
// 2.递归去偷，记录状态 // 执行用时：3 ms , 在所有 Java 提交中击败了 56.24% 的用户 public int rob1(TreeNode root) { Map<TreeNode, Integer> memo = new HashMap<>(); return robAction(root, memo); } int robAction(TreeNode root, Map<TreeNode, Integer> memo) { if (root == null) return 0; if (memo.containsKey(root)) return memo.get(root); int money = root.val; if (root.left != null) { money += robAction(root.left.left, memo) + robAction(root.left.right, memo); } if (root.right != null) { money += robAction(root.right.left, memo) + robAction(root.right.right, memo); } int res = Math.max(money, robAction(root.left, memo) + robAction(root.right, memo)); memo.put(root, res); return res; }
复杂度
时间复杂度：O ( n )
空间复杂度：O ( l o g n )
树形dp
- 确定递归函数的参数和返回值
参数：node
返回值：长度为2的dp数组，存放偷或者不偷的结果
下标为0记录不偷该节点所得到的的最大金钱
下标为1记录偷该节点所得到的的最大金钱。
- 确定终止条件
空节点时返回，{0,0}【相当于dp数组的初始化】
- 确定遍历顺序
后序遍历
- 确定单层递归逻辑
如果是偷当前节点，那么左右孩子就不能偷，val1 = cur->val + left[0] + right[0];
如果不偷当前节点，那么左右孩子就可以偷，至于到底偷不偷一定是选一个最大的，所以：val2 = max(left[0], left[1]) + max(right[0], right[1]);
最后当前节点的状态就是{val2, val1}; 即：{不偷当前节点得到的最大金钱，偷当前节点得到的最大金钱}
- 举例推导dp
代码
// 不偷：Max(左孩子不偷，左孩子偷) + Max(右孩子不偷，右孩子偷) // root[0] = Math.max(rob(root.left)[0], rob(root.left)[1]) + // Math.max(rob(root.right)[0], rob(root.right)[1]) // 偷：左孩子不偷+ 右孩子不偷 + 当前节点偷 // root[1] = rob(root.left)[0] + rob(root.right)[0] + root.val; public int rob3(TreeNode root) { int[] res = robAction1(root); return Math.max(res[0], res[1]); } int[] robAction1(TreeNode root) { int res[] = new int[2]; if (root == null) return res; int[] left = robAction1(root.left); int[] right = robAction1(root.right); res[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]); res[1] = root.val + left[0] + right[0]; return res; }
复杂度
时间复杂度：O ( n )
空间复杂度：O ( l o g n )
