# 968. Binary Tree Cameras 监控二叉树

@TOC

## # 题目描述

Given a binary tree, we install cameras on the nodes of the tree.

Each camera at a node can monitor `its parent, itself, and its immediate children`.

Calculate the minimum number of cameras needed to monitor all nodes of the tree.

Example 1:

``````Input: [0,0,null,0,0]
Output: 1
Explanation: One camera is enough to monitor all nodes if placed as shown.
``````

Example 2:

``````Input: [0,0,null,0,null,0,null,null,0]
Output: 2
Explanation: At least two cameras are needed to monitor all nodes of the tree. The above image shows one of the valid configurations of camera placement.
``````

Note:

1. The number of nodes in the given tree will be in the range `[1, 1000]`.
2. `Every` node has value 0.

## # 解题方法

1. 树中间的节点可以被当前节点、两个孩子节点、父亲节点四种方式覆盖。
2. 根节点，可以被当前节点、两个孩子节点三种方式覆盖。
3. 如果是叶子节点，可以被当前节点和父亲节点两种方式覆盖。

1. 如果这个节点是叶子节点，返回0
2. 如果这个节点是叶子节点的父节点，并且这个节点应该放相机，返回1
3. 如果这个节点被子节点覆盖了，并且这个节点没有相机，返回2.

1. 如果这个节点有子节点，并且这个子节点是叶子节点（节点0），那么当前节点需要相机0；
2. 如果这个节点有子节点，并且这个子节点放置了相机（节点1），那么当前节点被覆盖了；

C++代码如下：

``````/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int minCameraCover(TreeNode* root) {
if (dfs(root) == State::NONE)
++ans_;
return ans_;
}
private:
enum class State {NONE = 0, COVERED = 1, CAMERA = 2};
int ans_ = 0;
State dfs(TreeNode* root) {
if (!root) return State::COVERED;
State l = dfs(root->left);
State r = dfs(root->right);
if (l == State::NONE || r == State::NONE) {
++ans_;
return State::CAMERA;
}
if (l == State::CAMERA || r == State::CAMERA) {
return State::COVERED;
}
return State::NONE;
}
};
``````

## # 日期

2019 年 1 月 7 日 —— 新的一周开始啦啦啊