题目
给定一个二叉树，我们在树的节点上安装摄像头。
节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
计算监控树的所有节点所需的最小摄像头数量。
二叉树递归套路
以x为头的树,返回值有3中情况:
1) x上面无相机,但是x是被覆盖的,而且x底下所有节点都被覆盖了在这种情况下,请问需要几个相机
2) x上面有相机,x是被覆盖的,而且x底下所有节点都被覆盖了在这种情况下,请问需要几个相机
3) x既无相机,也没被覆盖,x底下所有节点都被覆盖了在这种情况下,请问需要几个相机
二叉树递归套路是说,如果我们想以x为头的整棵树都被覆盖了,需要哪些可能性?
那就两种可能性。第1种可能性就是x上面有相机,但是它被覆盖了。
第2种可能就是x上面无相机,但它被覆盖了
会少一种可能性,这种情况下你的这个两种可能性是不够的,收集信息的时候,我确实需要我的左树告诉我,它没被覆盖,但它底下都被覆盖的相机数量,因为我这儿放一个相机是可以补救他们的
二叉树的递归套路意义是什么?
意义就在于,他起码能够给你一个最初始的想法,你去分析答案的过程中。你肯定是要画与指数之间的拓扑关系去分析答案的,如果你发现你的可能性不够,你就往里加信息
为啥我要求x下方都被覆盖?很显而易见。因为x如果没被覆盖,它至少有它的父能补救他。但如果x下方的点没被覆盖,你往上返回爷爷辈的节点就再也无法补救,没有被覆盖的节点了
public static class TreeNode {
public int value;
public TreeNode left;
public TreeNode right;
}
public static int minCameraCover1(TreeNode root) {
Info data = process1(root);
return (int) Math.min(data.uncovered + 1, Math.min(data.coveredNoCamera, data.coveredHasCamera));
}
// 潜台词：x是头节点，x下方的点都被覆盖的情况下
public static class Info {
public long uncovered; // x没有被覆盖，x为头的树至少需要几个相机
public long coveredNoCamera; // x被相机覆盖，但是x没相机，x为头的树至少需要几个相机
public long coveredHasCamera; // x被相机覆盖了，并且x上放了相机，x为头的树至少需要几个相机
public Info(long un, long no, long has) {
uncovered = un;
coveredNoCamera = no;
coveredHasCamera = has;
}
}
// 所有可能性都穷尽了
public static Info process1(TreeNode X) {
if (X == null) { // base case
return new Info(Integer.MAX_VALUE, 0, Integer.MAX_VALUE);
}
Info left = process1(X.left);
Info right = process1(X.right);
// x uncovered x自己不被覆盖，x下方所有节点，都被覆盖
// 左孩子： 左孩子没被覆盖，左孩子以下的点都被覆盖
// 左孩子被覆盖但没相机，左孩子以下的点都被覆盖
// 左孩子被覆盖也有相机，左孩子以下的点都被覆盖
long uncovered = left.coveredNoCamera + right.coveredNoCamera;
// x下方的点都被covered，x也被cover，但x上没相机
long coveredNoCamera = Math.min(
// 1)
left.coveredHasCamera + right.coveredHasCamera,
Math.min(// 2)
left.coveredHasCamera + right.coveredNoCamera,
// 3)
left.coveredNoCamera + right.coveredHasCamera));
// x下方的点都被covered，x也被cover，且x上有相机
long coveredHasCamera =
Math.min(left.uncovered, Math.min(left.coveredNoCamera, left.coveredHasCamera))
+ Math.min(right.uncovered, Math.min(right.coveredNoCamera, right.coveredHasCamera))
+ 1;
return new Info(uncovered, coveredNoCamera, coveredHasCamera);
}优化
对于空树
只有一种解,被覆盖了没相机
所以面对这种最简单的情况,我们其实就是不放相机,恐怕后续的解会最优
因此我们只需给父节点返回一种信息就够了
当左树和右树只返回一种结果给父节点,那么父节点也只用返回一种信息给爷爷节点
我们需要记录节点的状态,有3种
1)没被覆盖
2)被覆盖了有相机
3)被覆盖了没有相机
可能性分析
1)左树或者右树有一个没被覆盖的,父节点只能放相机
2)左树或者右树都被覆盖,且有一棵树有相机,父节点会被子树的相机覆盖,因此不放相机
3)左树或者右树都被覆盖,且都没放相机,父节点返回没被覆盖,留给爷爷节点放相机
代码
public static int minCameraCover2(TreeNode root) {
Data data = process2(root);
return data.cameras + (data.status == Status.UNCOVERED ? 1 : 0);
}
// 以x为头，x下方的节点都是被covered，x自己的状况，分三种
public static enum Status {
UNCOVERED, COVERED_NO_CAMERA, COVERED_HAS_CAMERA
}
// 以x为头，x下方的节点都是被covered，得到的最优解中：
// x是什么状态，在这种状态下，需要至少几个相机
public static class Data {
public Status status;
public int cameras;
public Data(Status status, int cameras) {
this.status = status;
this.cameras = cameras;
}
}
public static Data process2(TreeNode X) {
if (X == null) {
return new Data(Status.COVERED_NO_CAMERA, 0);
}
Data left = process2(X.left);
Data right = process2(X.right);
int cameras = left.cameras + right.cameras;
// 左、或右，哪怕有一个没覆盖
if (left.status == Status.UNCOVERED || right.status == Status.UNCOVERED) {
return new Data(Status.COVERED_HAS_CAMERA, cameras + 1);
}
// 左右孩子，不存在没被覆盖的情况
if (left.status == Status.COVERED_HAS_CAMERA || right.status == Status.COVERED_HAS_CAMERA) {
return new Data(Status.COVERED_NO_CAMERA, cameras);
}
// 左右孩子，不存在没被覆盖的情况，也都没有相机
return new Data(Status.UNCOVERED, cameras);
}
