贪心算法:我要监控二叉树!
监控二叉树题目地址 : https://leetcode-cn.com/problems/binary-tree-cameras/ 给定一个二叉树,我们在树的节点上安装摄像头。 节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。 计算监控树的所有节点所需的最小摄像头数量。 示例 1: 输入:[0,0,null,0,0] 输出:1 解释:如图所示,一台摄像头足以监控所有节点。 示例 2: 输入:[0,0,null,0,null,0,null,null,0] 输出:2 解释:需要至少两个摄像头来监视树的所有节点。上图显示了摄像头放置的有效位置之一。 提示: 给定树的节点数的范围是 [1, 1000]。 每个节点的值都是 0。 思路 这道题目首先要想,如何放置,才能让摄像头最小的呢? 从题目中示例,其实可以得到启发,我们发现题目示例中的摄像头都没有放在叶子节点上! 这是很重要的一个线索,摄像头可以覆盖上中下三层,如果把摄像头放在叶子节点上,就浪费的一层的覆盖。 所以把摄像头放在叶子节点的父节点位置,才能充分利用摄像头的覆盖面积。 那么有同学可能问了,为什么不从头结点开始看起呢,为啥要...