LeetCode 968. 监控二叉树

题目

给定一个二叉树，我们在树的节点上安装摄像头。节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。计算监控树的所有节点所需的最小摄像头数量。

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

方法

因为计算最小摄像头数量，那么应该尽可能少的使用摄像头，所以叶子节点不能放摄像头，叶子节点的父节点放摄像头，并且每隔两层放置摄像头。为了实现该种放置方式应该从下到上遍历二叉树，即使用后序遍历
二叉树上节点一共存在三种状态：安装摄像头、未被覆盖和被覆盖，我们分别用 1、0 和 2 表示

• result 表示安装摄像头的个数
• 调用 traversal 函数，对二叉树进行从下到上的遍历，并判断根节点的状态。若根节点的状态为未被覆盖，那么表示该根节点应该安装摄像头，并且更新安装摄像头的数量

traversal 函数：对二叉树进行遍历

• 若为空节点，那么其状态为被覆盖，返回 2
  ※ 因为叶子节点的状态一定为被覆盖，不能安装摄像头，若空节点的状态为未覆盖，那么叶子节点需安装摄像头，不合理，所以空节点的状态为被覆盖
• left 表示遍历左孩子，right 表示遍历右孩子
• 若左右孩子的状态为被覆盖，那么此时该节点的状态应为未被覆盖
• 若左右孩子中至少有一个孩子的状态为未被覆盖，那么此时该节点的状态为安装摄像头，并且更新安装摄像头的数量
• 若左右孩子中至少有一个孩子的状态为安装摄像头，另一个孩子（或无）的状态为被覆盖，那么此时该节点的状态为被覆盖

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def minCameraCover(self, root: TreeNode) -> int:
        result = 0

        def traversal(node: TreeNode) -> int:
            nonlocal result

            if not node:
                return 2
            left = traversal(node.left)
            right = traversal(node.right)

            if left == 2 and right == 2:
                return 0
            elif left == 0 or right == 0:
                result += 1
                return 1
            elif left == 1 or right == 1:
                return 2
        
        if traversal(root) == 0:
            result += 1
        return result

参考

代码相关：https://programmercarl.com/0968.%E7%9B%91%E6%8E%A7%E4%BA%8C%E5%8F%89%E6%A0%91.html