#Problem

#⭐️⭐️⭐️⭐️⭐️

Binary Tree Camera

说给一个二叉树, 然后要放camera, 每个camera可以cover结点自己, children, 以及parent. 问最少放几个camera能把整个二叉树给cover住.

#Solution

#Solution #1 - Dynamic Programming

乍一看和House Robber III贼像无比. 如果刚刚做完House Robber III再来做这道题的话, 估计想也不想就直接开始写代码了.

我们来看一下如果用House Robber III的解法会出现什么问题:

对于每个结点, 依然是选还是不选的问题:

  1. 选 (放camera or 偷house)

    • 对于House Robber III来说, children就不能选了, 因为不能偷相邻的houses.

      dp[node] = node.val;
      dp[node] += dp[node.left.left] + dp[node.left.right];
      dp[node] += dp[node.right.left] + dp[node.right.right];

    • 对于Binary Tree Camera来说, children只是被cover了, 但至于children最终会不会被选, 是不一定的.

      dp[node] = 1;
      dp[node] += Math.min(dp[node.left], dp[node.left.left] + dp[node.left.right]);
      dp[node] += Math.min(dp[node.right], dp[node.right.left] + dp[node.right.right])

      • 这里可能会有疑问, 为什么不直接加上dp[node.left]和dp[node.right]就可以了,反正是左右子树的最优解, 管它有没有放camera. 为什么还要跟在下一层的结果作比较???
        • 这就是这道题最恶心的地方, 举个例子:
          • 1,2,3
          • dp[2] = 1; dp[3] = 1;
          • 如果算dp[1]的时候直接加左右子树的结果, dp[1]就等于3了. 但显然dp[1] = 1.
        • 这里背后的原因也就是要考虑parent cover children的情况.
          • dp[node.left]表示我只是在node放一个camera, 不管左右子树的结果.
          • dp[node.left.left] + dp[node.left.right]表示我在node放了一个camera, 并且这个camera cover了left child
          • 对于右子树也一样.
  2. 不选 (不放camera or 不偷house)

    • 对于House Robber III来说, 返回children的最优解即可, children选不选无所谓.
    • 对于Binary Tree Camera来说, 情况就复杂的多, 因为如果node不放camera, 我们就要考虑children来cover node的情况 (parent cover children的情况已经在 的情况中讨论了.)

      • 也就是说如果不选当前node, 那么at least one of its children much be picked.
      • 因此这道题一个dp数组就不能解决问题了. 至少还需要另一个dp_with[]数组来解决现在这种情况.

        • without = 0;
        • without += Math.min(dp_with[node.left] + dp[node.right], dp_with[node.right] + dp[node.left]);
        • dp[node] = Math.max(without, with);
      • 值得注意的一点就是at least one of its children must be picked

        • 如果选node.left, 右子树的选不选随意, dp[node] = dp_with[node.left] + dp[node.right]
        • 如果选node.right, 左子树选不选随意, dp[node] = dp_with[node.right] + dp[node.left]
      • 至于如何更新dp_with[node], 其实就是 的情况.

#Solution #2 - Greedy + BFS

这道题其实还有一种greedy解法要比上面DP的分析简单很多很多.

因为仔细想一下, 对于叶子结点Leaf来说, 是根本不可能放camera的. 肯定是放在parent of leaf划算.

因此最直接的方法就是把tree转换成一个graph, 然后循环一下步骤直到没有结点位置:

  1. remove all leaf nodes.
  2. res += (number of current leaf nodes)
  3. remove all leaf nodes. (parent of actual leaf)
  4. remove all leaf nodes. (parent of the node with camera)
  5. Go back to step 1.

这个方法代码写起来估计有点烦, 大神们连graph都不用建, 直接用遍历一遍tree就搞定. 自己欣赏吧.

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
public int dfs(TreeNode root) {
if (root == null) {
return NO_CAMERA_NEEDED.
}
int l = dfs(root.left);
int r = dfs(root.right);
if (l == NO_CAMERA || r == NO_CAMERA) {
res++;
return HAS_CAMERA;
} else if (l == HAS_CAMERA || r == HAS_CAMERA) {
return NO_CAMERA_NEEDED;
} else {
return NO_CAMERA;
}
}
```
#### Take Away
这道题如果没做过被考到的话, 估计DP解法是死都做不对的. 所以分析一下理解理解就可以了, 主要就是和House Robber III区分开来. 然后greedy + dfs的解法估计不是个神仙也是想不到的.
所以如果真的背考到, 个人觉得从Greedy + Graph + BFS的思路入手会比较直观好理解, 思路清晰一些代码还是可以写的. 上来就DP或者greedy + dfs显然就是背答案了, 而且背的不好把自己给绕晕了. 就像一开始做这道题用DP做了几个小时也没做对.
#### Code
##### Solution #1 - DP - Java
```java
class Solution {
private Map<TreeNode, Integer> dp = new HashMap<>();
private Map<TreeNode, Integer> dp_with = new HashMap<>();
public int minCameraCover(TreeNode root) {
if (root == null) return 0;
if (root.left == null && root.right == null) return 1;
if (dp.containsKey(root)) return dp.get(root);
int res = 0;
if (root.left == null) {
res = withCamera(root.right);
} else if (root.right == null) {
res = withCamera(root.left);
} else {
int a = withCamera(root);
int b = withCamera(root.left) + minCameraCover(root.right);
int c = withCamera(root.right) + minCameraCover(root.left);
res = Math.min(a, Math.min(b, c));
}
dp.put(root, res);
return res;
}
private int withCamera(TreeNode root) {
if (root == null) return 0;
if (dp_with.containsKey(root)) return dp_with.get(root);
int res = 1;
if (root.left != null) res += Math.min(withCamera(root.left), minCameraCover(root.left.left) + minCameraCover(root.left.right));
if (root.right != null) res += Math.min(withCamera(root.right), minCameraCover(root.right.left) + minCameraCover(root.right.right));
dp_with.put(root, res);
return res;
}
}
#Solution #2 - Greedy - Java
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
class Solution {
private static final int LEAF = 0;
private static final int HAS_CAMERA = 1;
private static final int NO_NEED_CAMERA = 2;
int res = 0;
public int minCameraCover(TreeNode root) {
if (root == null) return 0;
if (dfs(root) == LEAF) res++;
return res;
}
private int dfs(TreeNode root) {
if (root == null) return NO_NEED_CAMERA;
if (root.left == null && root.right == null) return LEAF;
int l = dfs(root.left);
int r = dfs(root.right);
if (l == LEAF || r == LEAF) {
res++;
return HAS_CAMERA;
} else if (l == HAS_CAMERA || r == HAS_CAMERA) {
return NO_NEED_CAMERA;
} else {
return LEAF;
}
}
}

Comments