子寒的博客
0%

leetcode968 Binary Tree Cameras 解题报告

发表于 更新于 分类于

英文原题

Given a binary tree, we install cameras on the nodes of the tree.

Each camera at a node can monitor its parent, itself, and its immediate children.

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

Example

分析

    题目大致意思是给树装监控，一个监控可以覆盖自己以及它的父节点和子节点，求最少需要多少个监控。     首先分析每个节点会被如何覆盖：

  • 第一种，根节点，左右子节点里有监控。
  • 第二种，中间节点，父节点或左右子节点有监控。
  • 第三种，子节点，父节点有监控。
  • 最后是本身就是监控。     肯定是要用DFS遍历来模拟安装监控的，但是这题我们得从下往上安装。设定三个状态0:未被覆盖；1:被覆盖；2:本身是监控。那么对于每个节点来说，如果是叶子节点，那就不用安装；对于其他节点来说，则根据其子节点的覆盖情况来安装。这么做就不需要把父节点考虑进来，方便很多。

python 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def minCameraCover(self, root: TreeNode) -> int:
        res = [0]
        
        ## 0: not covered; 1: covered; 2: camera
        def dfs(root):
            if not root:
                return 1
            left = dfs(root.left)
            right = dfs(root.right)
            
            if left == 0 or right == 0:
                res[0] += 1
                return 2
            if left == 2 or right == 2:
                return 1
            return 0
        
        if dfs(root) == 0:
            res[0] += 1
        return res[0]

前两天打了疫苗有点发烧就没更新，今天继续。