今日算法之_158_监控二叉树
前言
Github：https://github.com/HealerJean
1、
给定一个二叉树，我们在树的节点上安装摄像头。
节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
计算监控树的所有节点所需的最小摄像头数量。
示例 1：
输入：[0,0,null,0,0]
输出：1
解释：如图所示，一台摄像头足以监控所有节点。
示例 2：
输入：[0,0,null,0,null,0,null,null,0]
输出：2
解释：需要至少两个摄像头来监视树的所有节点。 上图显示了摄像头放置的有效位置之一。
1.1、解题思路
分析：
如果 root 处安放摄像头，则孩子 left,right 一定也会被监控到。此时，只需要保证left 和right 的两棵子树都被覆盖即可。
如果 root 处不安放摄像头，则除了root两棵子树需要被覆盖之外，孩子 left,right 之一必须要安装摄像头，从而保证root 会被监控到。
讨论： 因此本层的状态是由下一层的状态而决定的，而状态根据这样来分析得到的：一个摄像头最多影响3层（本层、下一层、上一层）；
1、 下一层如果能被观测到但没有摄像头，那么本层肯定是不被观测得到的（0->1）；
2、 如果下一层安装了摄像头，本层能够被观测到（2->0）；
3、 下一层如果不能被观测得到，那么本层一定安装了摄像头（1->2）。 ps：括号内容为 下一层状态为a 决定 本层状态为b
实战：0=>这个结点待覆盖，1=>这个结点已经覆盖， 2=>这个结点上安装了相机
1.2、算法
/**
* 0=>没有覆盖，这个结点待覆盖，1=>这个结点已经覆盖， 2=>这个结点上安装了相机
*/
int count = 0;
public int minCameraCover(TreeNode root) {
//如果当前结点没有被覆盖的话，说明当前结点要安装一个摄像头
if (dfs(root) == 0) {
count++;
}
return count;
}
/**
* 本层的状态是由下一层的状态而决定的，0=>没有覆盖，这个结点待覆盖，1=>这个结点已经覆盖， 2=>这个结点上安装了相机
*/
public int dfs(TreeNode root) {
//空节点设为已覆盖（空的肯定不用搭理，就表示已覆盖了吧）
if (root == null) {
return 1;
}
int left = dfs(root.left);
int right = dfs(root.right);
//左右两个节点都没有覆盖，说明当前结点要安装摄像头
if (left == 0 || right == 0) {
count++;
return 2;
// 子节点均被监视，则当前节点需要被覆盖，返回待覆盖0（本层状态由下一层决定，下一层都监视了。不管 子集）
} else if (left == 1 && right == 1) {
return 0;
// left + right >= 3 //子节点至少有一个安装了摄像头，则当前节点被覆盖了
// 1、left + right = 4 子节点都是已安装摄像头
// 2、 left + right = 3 子节点至少有一个摄像头
} else {
return 1;
}
}
1.3、测试
@Test
public void test(){
System.out.println(minCameraCover(initTreeNode()));
}
public TreeNode initTreeNode(){
TreeNode treeNode1 = new TreeNode(3, null ,null);
TreeNode treeNode2 = new TreeNode(6, null , null);
TreeNode treeNode3 = new TreeNode(4, treeNode1, treeNode2);
TreeNode treeNode4 = new TreeNode(1, null, null);
TreeNode root = new TreeNode(5, treeNode3, treeNode4);
return root ;
}
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
TreeNode(int x, TreeNode left, TreeNode right) {
this.val = x;
this.left = left;
this.right = right;
}
}
