贪心
解题思路
题目示例中的摄像头都没有放在叶子节点上，摄像头可以覆盖上中下三层；
怎样才能充分利用摄像头的覆盖面积？
- 头结点放不放摄像头也就省下一个摄像头，叶子节点放不放摄像头省下了的摄像头数量是指数阶别的；
- 所以要从下往上看，局部最优：让叶子节点的父节点安摄像头，所用摄像头最少，整体最优：全部摄像头数量所用最少；
可利用 后续遍历 从下到上遍历二叉树的节点；
如何隔两个节点放一个摄像头？
- 可以设置三种状态：该节点无覆盖 => 0、本节点有摄像头 => 1、本节点有覆盖 => 2；
- 为了让摄像头数量最少，要尽量让叶子节点的父节点安装摄像头，才能摄像头的数量最少，则自底向上层层设置 2 => 1 => 0 => 2 => 1 => 0 => … 状态；
- 那么空节点不能是无覆盖的状态，这样叶子节点就要放摄像头了，空节点也不能是有摄像头的状态，这样叶子节点的父节点就没有必要放摄像头了，而是可以把摄像头放在叶子节点的爷爷节点上；
- 所以空节点的状态只能是有覆盖，这样就可以在叶子节点的父节点放摄像头了；
主要有如下四类情况：
- 情况 1：左右节点都 有覆盖 状态，则父节点一定是 无覆盖 状态，之后会将爷爷节点再设置成 有摄像头 状态，如果没有爷爷节点了那其实就是
情况 4已经递归到根节点了；
- 情况 2：左右节点至少有一个 无覆盖 状态，则父节点一定是 有摄像头 状态；
- 情况 3：左右节点至少有一个 有摄像头 状态，但不能是 无覆盖 状态，则父节点一定是 有覆盖 状态；
- 情况 4：根结点 没有覆盖 状态，递归结束后 根结点 需要特殊处理，如果根节点是 无覆盖 则需要将根节点设置成 有摄像头 状态；
复杂度
-
时间复杂度：
O(n)，其中 n 为二叉树的节点个数； -
空间复杂度：
O(n)，最坏情况下，二叉树是一条链，递归需要O(n)的栈空间；
代码实现
var minCameraCover = function (root) {
let result = 0;
function traversal(cur) {
// 空节点，该节点有覆盖
if (cur === null) return 2;
let left = traversal(cur.left);
let right = traversal(cur.right);
// 情况 1：左右节点都有覆盖
if (left === 2 && right === 2) return 0;
// 情况 2：左右节点至少有一个 无覆盖 的情况
if (left === 0 || right === 0) {
result++;
return 1;
}
// 情况 3：左右节点至少有一个有摄像头，但不能是 无覆盖 状态
if (left === 1 || right === 1) return 2;
}
// 情况 4：头结点 没有覆盖 状态
if (traversal(root) === 0) result++;
return result;
};
参考资料
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 738. 单调递增的数字
上一篇
评论
