0968. Binary Tree Cameras

题目信息

题号:

0968

难度:

Hard

主题:

二叉树、监控覆盖、最少摄像头

原题:

LeetCode 0968

重点:

摄像头只能安装在树节点上,并同时监控该节点、父节点和直接左右孩子;必须覆盖全部节点且最小化摄像头数量

题目重述

给定一棵二叉树的根节点 root。可以在任意树节点上安装摄像头。一个摄像头能够监控它所在的节点、该节点的父节点以及该节点直接连接的左孩子和右孩子。

请返回监控树中全部节点所需的最少摄像头数量。摄像头不能监控距离超过一条边的节点,空孩子无需覆盖。

树中节点数在 [1, 1000] 范围内,节点值均为 0。

自建示例

两层分支需要两个摄像头:

输入:root = [0,0,0,null,null,0,0]
输出:2
解释:在根节点安装摄像头可覆盖根及两个孩子;还需在右孩子安装一个摄像头,才能覆盖它的两个孩子,因此最少为 2。

树只有一个节点:

输入:root = [0]
输出:1
解释:唯一节点必须被监控,只能在它自身安装一个摄像头。