968. Binary Tree Cameras
解题思路
题目让我们在一棵二叉树上安装摄像头，摄像头可以观察相邻的节点，要求我们求出能观察到完整的二叉树所需的最少摄像头个数
首先，要想让摄像头个数最少，必须让每一个摄像头的观察范围最大，这就表示我们应该尽可能的在叶子节点的父节点上安装摄像头
为了达到这个目的，我们考虑一种从下晚上遍历整个树的方法，后序遍历（左子树 -> 右子树 -> 根节点）
我们观察到，加入摄像头之后，二叉树的节点会有三种情况：
- 未覆盖，我们记为 0
- 有摄像头： 我们记为 1
- 已覆盖： 我们记为 2
接下来，我们的目的就是在后序遍历二叉树的时候，为每个节点判断状态：
首先是空节点，空节点肯定不能放摄像头，所以不会是状态 1；其次，如果我们把空节点记为状态 0 未覆盖的话，遍历到叶子节点的时候就必须放摄像头了，这个与我们的原则不符。所以空节点都记为状态 2，已覆盖
其次，当我们更新到中间任意节点的时候，会有四种可能：
- 左节点跟右节点都有覆盖了
left == 2 && right == 2：这种情况我们就把当前节点设置为 0，未覆盖 - 左节点跟右节点有一个是未覆盖
left == 0 || right == 0：这种情况我们必须把当前节点设置为 1，放一个摄像头 - 左节点跟有节点至少有一个放了摄像头
left == 1 || right == 1：我们把当前节点设置为 2，已覆盖 - 最后，当我们遍历到根节点的时候，如果根节点的状态是 0，则需要为根节点再加一个摄像头
C++
class Solution {
public:
int res = 0;
int minCameraCover(TreeNode* root) {
// 0: 无覆盖
// 1: 有摄像头
// 2: 有覆盖
if(traversal(root) == 0) {
res++;
}
return res;
}
int traversal(TreeNode* root) {
if(root == nullptr) {
return 2;
}
int left = traversal(root->left);
int right = traversal(root->right);
// 如果两个都有覆盖了
if(left == 2 && right == 2) {
return 0;
}
// 如果其中一个子节点没有覆盖，在当前节点放一个摄像头
if(left == 0 || right == 0) {
res++;
return 1;
}
// 如果至少一个子节点有摄像头
if(left = 1 || right == 1) {
return 2;
}
// 这里永远不会走到
return -1;
}
};
Javascript
var minCameraCover = function(root) {
// 摄像头个数
let res = 0;
// 0: 无覆盖
// 1: 有摄像头
// 2: 有覆盖
let traversal = (node) => {
// 空节点：有覆盖
if(node == null) {
return 2;
}
// 左子树 -> 右子树 -> 父节点
let left = traversal(node.left);
let right = traversal(node.right);
// 如果左右节点都覆盖了，表示当前节点还没被覆盖
if(left === 2 && right === 2) {
return 0;
}
// 如果其中一个子节点还没被覆盖，则在当前节点加一个摄像头
if(left === 0 || right === 0) {
res++;
return 1;
}
// 如果其中一个子节点有摄像头，当前节点就是有覆盖状态
if(left === 1 || right === 1) {
return 2;
}
}
// 如果遍历到根节点发现根节点是没覆盖的，要加一个摄像头在根节点上
if(traversal(root) === 0) {
res++;
}
return res;
};