Keshawn_lu's Blog

Leetcode 968. 监控二叉树

树 深度优先搜索
字数统计: 555阅读时长: 2 min
2020/09/22 Share

题目简介：

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

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

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

示例 1：

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

示例 2：

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

提示：

  1. 给定树的节点数的范围是 [1, 1000]。
  2. 每个节点的值都是 0。

思路：

后序遍历，自下而上的来解决问题。

我们将结点的状态分为三种情况：

  1. 结点未被覆盖(0)
  2. 结点已被覆盖(1)
  3. 结点上设置了摄像头(2)

对于一个结点root，根据它的两个孩子结点的状态，一共可分为三种情况：

  1. 两个孩子至少有一个未被覆盖到，那么此时需要在root上设置摄像头(2)
  2. 两个孩子已经被覆盖到了(但都没有设置摄像头)，此时root未被覆盖到(0)，这个时候root设置摄像头是不划算的，交给其父节点去规划即可。
  3. 两个孩子中至少有一个设置了摄像头，那么此时root被覆盖到了(1)

若最后的根结点未被覆盖到，则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
42
43
44
45
46
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:

    int res = 0;

    int dfs(TreeNode* root){

        if(!root)
            return 1;

        int left = dfs(root -> left);
        int right = dfs(root -> right);

        // 0.未被覆盖, 1.被覆盖, 2.需安置摄像头
        if(left == 0 || right == 0){    //孩子均未被覆盖

            res++;
            return 2; 
        }

        if(left == 1 && right == 1)
            return 0;
        
        if(left == 2 || right == 2) //左右孩子已有一个有摄像头
            return 1;
        
        return 5555;   //随便返回
    }

    int minCameraCover(TreeNode* root) {

        if(dfs(root) == 0)  //root未被覆盖时, 加一个摄像头
            res++;
        
        return res;
    }
};
CATALOG
  1. 1. 题目简介：
  2. 2. 思路：
  3. 3. 代码如下：
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网