Leetcode 968.监控二叉树

题目要求

  • 给定一个二叉树，我们在树的节点上安装摄像头。

  • 节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。

  • 计算监控树的所有节点所需的最小摄像头数量。

示例 1：

输入：[0,0,null,0,0]
输出：1
解释：如图所示，一台摄像头足以监控所有节点。

示例 2:

输入：[0,0,null,0,null,0,null,null,0]
输出：2
解释：需要至少两个摄像头来监视树的所有节点。 上图显示了摄像头放置的有效位置之一。

贪心

思路：

节点的三种状态：
0：无覆盖
1：有摄像头
2：有覆盖

递归的四种情况：

  1. 左右节点都有覆盖
    左孩子有覆盖，右孩子有覆盖，那么此时中间节点应该就是无覆盖的状态了。

    代码如下：
1
2
3
if (left == 2 && right == 2) {
    return 0;
}
  1. 左右节点至少有一个无覆盖
    如果是以下情况，则中间节点（父节点）应该放摄像头：
  • left == 0 && right == 0 左右节点无覆盖
  • left == 1 && right == 0 左节点有摄像头，右节点无覆盖
  • left == 0 && right == 1 左节点有无覆盖，右节点摄像头
  • left == 0 && right == 2 左节点无覆盖，右节点覆盖
  • left == 2 && right == 0 左节点覆盖，右节点无覆盖

此时摄像头的数量要加一，并且return 1，代表中间节点放摄像头。

代码如下：

1
2
3
4
else if (left == 0 || right == 0) {
    res++;
    return 1;
}
  1. 左右节点至少有一个有摄像头
    如果是以下情况，则中间节点（父节点）应该有覆盖：
  • left == 1 && right == 2 左节点有摄像头，右节点有覆盖
  • left == 2 && right == 1 左节点有覆盖，右节点有摄像头
  • left == 1 && right == 1 左右节点都有摄像头

代码如下：

1
2
3
else {
    return 2;
}
  1. 根节点的状态

以上都处理完了，递归结束之后，可能头结点 还有一个无覆盖的情况，如图：

所以递归结束之后，还要判断根节点，如果没有覆盖，res++，代码如下：

1
2
3
4
5
6
public int minCameraCover(TreeNode root) {
        if(minCame(root)==0){
            res++;
        }
        return res;
    }
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
class Solution {
    int  res=0;
    public int minCameraCover(TreeNode root) {
        // 对根节点的状态做检验,防止根节点是无覆盖状态 .
        if(traversal(root)==0){
            res++;
        }
        return res;
    }
    /**
     节点的状态值：
       0 表示无覆盖
       1 表示 有摄像头
       2 表示有覆盖
    后序遍历，根据左右节点的情况,来判读 自己的状态
     */
    public int traversal(TreeNode root){
        if(root==null){
            // 空节点默认为 有覆盖状态，避免在叶子节点上放摄像头
            return 2;
        }
        int left=traversal(root.left);
        int  right=traversal(root.right);

        // 如果左右节点都覆盖了的话, 那么本节点的状态就应该是无覆盖,没有摄像头
        if(left==2&&right==2){
            //(2,2)
            return 0;
        }else if(left==0||right==0){
            // 左右节点都是无覆盖状态,那 根节点此时应该放一个摄像头
            // (0,0) (0,1) (0,2) (1,0) (2,0)
            // 状态值为 1 摄像头数 ++;
            res++;
            return 1;
        }else{
            // 左右节点的 状态为 (1,1) (1,2) (2,1) 也就是左右节点至少存在 1个摄像头，
            // 那么本节点就是处于被覆盖状态
            return 2;
        }
    }
}