968. Binary Tree Cameras

968. Binary Tree Cameras

Question

You are given the root of a binary tree. We install cameras on the tree nodes where each camera at a node can monitor its parent, itself, and its immediate children.

Return the minimum number of cameras needed to monitor all nodes of the tree.

Solution 1

贪心算法,后序遍历。每次递归根据下面两个子节点的状态来决定当前节点的状态。

每个节点一共有三种状态:

  1. 未被监控,返回0。
  2. 摄像头,返回1。
  3. 已被监控,返回2。

递归,当当前节点为空,则返回2,表示已被监控。这样叶子节点则为未被监控的状态。

如果下面的子节点有一个未被监控,则当前节点需要设置相机,返回1,计数res+1。
如果下面的子节点有一个为摄像头,则当前节点已被监控,返回2。
否则下面的节点均为已被监控,此时返回未被监控0。

Code

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
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
int res = 0; //记录摄像头个数
public int minCameraCover(TreeNode root) {
if(judge(root) == 0) res++; //如果根节点未被监控,则需要增加一个摄像机
return res;
}
public int judge(TreeNode root){
if(root == null) return 2; //根节点为空时返回2,这样叶子节点变为未被监控
int left = judge(root.left);
int right = judge(root.right);

if(left == 0 || right == 0){ //如果左右子节点有未被监控的节点,则当前节点设置为摄像机,结果加一,返回1
res++;
return 1;
}
if(left == 1 || right == 1) return 2; //如果左右子节点中有摄像机,则当前节点已被监控,返回2
return 0; //如果左右子节点都被监控,则当前节点未被监控,返回0
}
}

Solution 2

参考:从递归优化到树形DP

树形DP。
递归,每次返回当前节点所有子节点的最小相机数。
每一个节点有三种状态:

  1. 放置了相机。
  2. 没有相机,但是被父节点parent监控。
  3. 没有相机,但是被子节点son监控。

将三种状态分别传入minCam()方法。

递归方法 minCam()

在递归时传入两个参数hasCamera和isWatched,来判断当前节点是否有相机,是否被监控。
当当前节点为空节点时,如果设置应当有相机(做不到)则返回无限大,消除这个返回值。如果不应该有相机,则返回0。

向下递归子节点。

  • 当当前节点应该有相机时:
    子节点一定被监控因此isWatched为true。
    子节点可以放置或不放置相机,因此hasCamera可以为true或false。
    注意当前位置放置相机,则子节点最多放置一个相机,因此一共有三种组合。
    由于相机至少有一个,因此返回其中的最小值+1。
  • 当当前节点没有放置相机,但被父节点监控时:
    左右节点一共有四种组合,分别同时将子节点的监控状态向下递归。
    返回其中的最小值。
  • 当当前节点没有放置相机,也没有被父节点监控,而是被子节点监控时:
    子节点至少有一个相机,向下递归状态,一共有三种组合。
    返回其中的最小值

然后分别调用minCam(root, true, true)和minCam(root, false, fasle),取两者中的小值,即可得到答案。

树形dp优化剪枝

上面的方法实际采用时会超时,因为我们重复了三次调用一个子树下的三种状态的minCam。
因此我们可以将三种状态下的minCam分别保存在数组中返回。

  1. withCam: 当前子树root有相机。
  2. noCamWatchedByParent: 当前子树root没有相机,被父节点监控。
  3. noCamWatchedBySon: 当前子树root没有相机,被子节点监控。

在每次递归时,获取数组minCam(root.left)和minCam(root.right)。
然后根据左右子节点的三个参数来计算当前节点的新的三个参数,将其返回。

Code

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
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int minCameraCover(TreeNode root) {
return Math.min(minCam(root, true, true), minCam(root, false, false));
}

private int minCam(TreeNode root, boolean hasCamera, boolean isWatched){
if(root == null) return hasCamera ? Integer.MAX_VALUE / 2 : 0;

if(hasCamera){
int min = Math.min(minCam(root.left, false, true) + minCam(root.right, false, true), minCam(root.left, true, true) + minCam(root.right, false, true));
min = Math.min(min, minCam(root.left, false, true) + minCam(root.right, true, true));
return 1 + min;
}
else if(isWatched){
int min = Math.min(minCam(root.left, true, true) + minCam(root.right, true, true), minCam(root.left, true, true) + minCam(root.right, false, false));
min = Math.min(min, minCam(root.left, false, false) + minCam(root.right, true, true));
min = Math.min(min, minCam(root.left, false, false) + minCam(root.right, false, false));
return min;
}
else{
int min = Math.min(minCam(root.left, true, true) + minCam(root.right, true, true), minCam(root.left, true, true) + minCam(root.right, false, false));
min = Math.min(min, minCam(root.left, false, false) + minCam(root.right, true, true));
return min;
}
}
}

Code

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
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int minCameraCover(TreeNode root) {
int[] res = minCam(root);
return Math.min(res[0], res[2]);
}

private int[] minCam(TreeNode root){
if(root == null){
return new int[] {Integer.MAX_VALUE/2, 0, 0};
}
int[] left = minCam(root.left);
int[] right = minCam(root.right);

int withCam = 1 + Math.min(left[1] + right[1], Math.min(left[0] + right[1], left[1] + right[0]) );
int noCamWatchedByParent = Math.min( left[0] + right[0], Math.min( left[0] + right[2], Math.min( left[2] + right[0], left[2] + right[2] )));
int noCamWatchedBySon = Math.min( left[0] + right[0], Math.min( left[0] + right[2], left[2] + right[0]));
return new int[] {withCam, noCamWatchedByParent, noCamWatchedBySon};
}
}
Author

Xander

Posted on

2022-06-18

Updated on

2022-06-17

Licensed under

Comments