0968. Binary Tree Cameras ========================= 题目信息 -------- :题号: 0968 :难度: Hard :主题: 二叉树、监控覆盖、最少摄像头 :原题: `LeetCode 0968 `_ :重点: 摄像头只能安装在树节点上,并同时监控该节点、父节点和直接左右孩子;必须覆盖全部节点且最小化摄像头数量 题目重述 -------- 给定一棵二叉树的根节点 ``root``。可以在任意树节点上安装摄像头。一个摄像头能够监控它所在的节点、该节点的父节点以及该节点直接连接的左孩子和右孩子。 请返回监控树中全部节点所需的最少摄像头数量。摄像头不能监控距离超过一条边的节点,空孩子无需覆盖。 树中节点数在 ``[1, 1000]`` 范围内,节点值均为 ``0``。 自建示例 -------- 两层分支需要两个摄像头: .. code-block:: text 输入:root = [0,0,0,null,null,0,0] 输出:2 解释:在根节点安装摄像头可覆盖根及两个孩子;还需在右孩子安装一个摄像头,才能覆盖它的两个孩子,因此最少为 2。 树只有一个节点: .. code-block:: text 输入:root = [0] 输出:1 解释:唯一节点必须被监控,只能在它自身安装一个摄像头。