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