

LeetCode: 968. 监控二叉树

• LeetCode: 968. 监控二叉树
  • 1、题目描述
  • 2、解题思路

1、题目描述

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

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

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

示例 1：

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

示例 2：

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

提示：

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

2、解题思路

• 使用不同的状态表示当前节点是否被监控
• 如果是叶子节点，就返回1，表示需要监控
• 如果当前节点中左右节点需要监控，那么就放摄像头，返回2
• 如果子节点是2，表示当前节点被子节点监控，返回0，表示重新开始

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def minCameraCover(self, root: TreeNode) -> int:
        """
        状态值：
           0：None
           1：等待监控
           2：有摄像头
        :param root:
        :return:
        """
        res = 0

        def dfs(node):
            nonlocal res
            if not node:
                return 0

            left = dfs(node.left)
            right = dfs(node.right)

            if left == 0 and right == 0:
                return 1
            if left == 1 or right == 1:
                res += 1
                return 2
            if left == 2 or right == 2:
                return 0

        if dfs(root) == 1:
            res += 1
        return res