0968. 监控二叉树 #
- 标签:树、深度优先搜索、动态规划、二叉树
- 难度:困难
题目大意 #
给定一个二叉树,需要在树的节点上安装摄像头。节点上的每个摄影头都可以监视其父节点、自身及其直接子节点。
计算监控树的所有节点所需的最小摄像头数量。
- 示例 1:
|
|
- 示例 2:
|
|
解题思路 #
根据题意可知,一个摄像头的有效范围为 3 层:父节点、自身及其直接子节点。而约是下层的节点就越多,所以摄像头应该优先满足下层节点。可以使用后序遍历的方式遍历二叉树的节点,这样就可以优先遍历叶子节点。
对于每个节点,利用贪心思想,可以确定三种状态:
- 第一种状态:该节点无覆盖
- 第二种状态:该节点已经装上了摄像头
- 第三种状态:该节点已经覆盖
为了让摄像头数量最少,我们要尽量让叶⼦节点的⽗节点安装摄像头,这样才能摄像头的数量最少。对此我们应当分析当前节点和左右两侧子节点的覆盖情况。
先来考虑空节点,空节点应该算作已经覆盖状态。
再来考虑左右两侧子覆盖情况:
- 如果左节点或者右节点都无覆盖,则当前节点需要装上摄像头,答案 res 需要 + 1。
- 如果左节点已经覆盖或者右节点已经装上了摄像头,则当前节点已经覆盖。
- 如果左节点右节点都已经覆盖,则当前节点无覆盖。
根据以上条件就可以写出对应的后序遍历代码。
代码 #
|
|