AlgoPressAppearance
0968-监控二叉树
https://leetcode.cn/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。
思路【官方：树形dp】
https://leetcode.cn/problems/binary-tree-cameras/solution/jian-kong-er-cha-shu-by-leetcode-solution/
以节点 root 为例，包含三种状态 (这三种状态很难想到)
状态0 : root 处必须放置摄像头，所需要的最大摄像头数
状态1 : 不管 root 处有没有放置摄像头，所需要的最大摄像头数
状态2 : 覆盖左右两棵子树，所需要的最大的摄像头数
状态0 = L2 + R2 + 1
状态1 = min(状态0, min(L0+R2,L2+R0)) 即root自己放，或者左右子树放一个覆盖root
参考代码
csharp
public class Solution {
private int[] dfs(TreeNode root){
if(root == null){
return new int[]{int.MaxValue / 2, 0, 0};
}
int[] left = dfs(root.left);
int[] right = dfs(root.right);
int[] arr = new int[3];
arr[0] = left[2] + right[2] + 1;
arr[1] = Math.Min(arr[0],Math.Min(left[0] + right[1], left[1] + right[0]));
arr[2] = Math.Min(arr[0],left[1]+right[1]);
return arr;
}
public int MinCameraCover(TreeNode root) {
int[] arr = dfs(root);
return arr[1];
}
}
思路2【贪心算法】 思路真棒
节点的3种状态
- 0 : 该节点无覆盖
- 1 : 该节点有摄像头
- 2 : 该节点有覆盖 如果该节点没有摄像头，那么他属于 0 或者 2 的一种
贪心算法，就是尽量安装子节点的父亲(当子节点的子节点为空的时候) 空节点的状态应该属于 2，因为他不能装摄像头，但是也不用覆盖他，摄像头撞到空节点的爷爷即可
参考代码
csharp
public class Solution {
private int result = 0;
private int dfs(TreeNode root){
if(root == null){
return 2;
}
int left = dfs(root.left);
int right = dfs(root.right);
//根据左右状态推断当前摄像头状态，如果必须安装，则 result + 1
if(left == 0 || right == 0){
result++;
return 1;
}
if(left == 1 || right == 1){
return 2;
}
if(left == 2 && right == 2){
return 0;
}
return -1;
}
public int MinCameraCover(TreeNode root) {
if(dfs(root) == 0){
result++;
}
return result;
}
}
参考代码：默写 2022-03-22
csharp
public class Solution {
//贪心算法：最子节点不要安装，尽量安装他的父亲，然后爷爷那里也不用安装
//定义三种状态： 很重要
// 1. 该节点有摄像头
// 2. 该节点有覆盖 (就是会被灯照到)
// 0. 该节点无覆盖 (就是灯照不到)
// 没有安装等 就属于(0,2)的一种情况
// 特殊情况节点为 null 应该是属于2.有覆盖，因为只要他的爷爷装了摄像头，就算是覆盖成功的。
// 通过 dfs 来计算节点是否需要安装摄像头
int result = 0;
private int dfs(TreeNode root){
if(root == null){
return 2;
}
int left = dfs(root.left);
int right = dfs(root.right);
if(left == 0 || right == 0){ //如果任何一个子节点没有被覆盖，自己必须安装摄像头
result++;
return 1;
}
else if(left == 1 || right == 1){ //如果任何一个子节点安装了摄像头，说明自己被覆盖了
return 2;
}
//剩下的情况说明都是两个节点都是2，被其他节点覆盖了，所以当前节点无覆盖
return 0;
}
public int MinCameraCover(TreeNode root) {
if(dfs(root) == 0){
result++;
}
return result;
}
}