---
# System prepended metadata

title: LC 968. Binary Tree Cameras
tags: [Binary Tree, leedcode, Greedy, hard, python, c++]

---

# LC 968. Binary Tree Cameras

### [Problem link](https://leetcode.com/problems/binary-tree-cameras/)

###### tags: `leedcode` `python` `c++` `hard` `Greedy` `Binary Tree`

You are given the <code>root</code> of a binary tree. We install cameras on the tree nodes where each camera at a node can monitor its parent, itself, and its immediate children.

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

**Example 1:** 
<img alt="" src="https://assets.leetcode.com/uploads/2018/12/29/bst_cameras_01.png" style="width: 138px; height: 163px;" />
```
Input: root = [0,0,null,0,0]
Output: 1
Explanation: One camera is enough to monitor all nodes if placed as shown.
```

**Example 2:** 
<img alt="" src="https://assets.leetcode.com/uploads/2018/12/29/bst_cameras_02.png" style="width: 139px; height: 312px;" />
```
Input: root = [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.
```

 **Constraints:** 

- The number of nodes in the tree is in the range <code>[1, 1000]</code>.
- <code>Node.val == 0</code>


## Solution 1 - Greedy
#### Python
```python=
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def minCameraCover(self, root: Optional[TreeNode]) -> int:
        self.res = 0

        def traversal(cur):

            if not cur:
                return 2
            left = traversal(cur.left)
            right = traversal(cur.right)

            if left == 0 or right == 0:
                self.res += 1
                return 1
            elif left == 1 or right == 1:
                return 2

            return 0

        tmp = traversal(root)
        if tmp == 0:
            self.res += 1

        return self.res
```
#### C++
```cpp=
class Solution {
public:
    const int NOCOVER = 0;
    const int COVER = 1;
    const int CAMERA = 2;
    int res = 0;

    int traversal(TreeNode *cur) {
        if (cur == nullptr) {
            return COVER;
        }
        int left = traversal(cur->left);
        int right = traversal(cur->right);
        if (left == NOCOVER || right == NOCOVER) {
            res++;
            return CAMERA;
        } else if (left == COVER && right == COVER) {
            return NOCOVER;
        } else {
            return COVER;
        }
    }

    int minCameraCover(TreeNode* root) {
        if (traversal(root) == NOCOVER) {
            res++;
        }
        return res;
    }
};
```

>### Complexity
>n = The number of nodes
>|             | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1  | O(n)            | O(1)             |

## Note
sol1:
python:
>0: no cover
>1: has camera
>2: covered

| left | right | return |
| ---- | ----- | ------ |
| 0    | 0     | 1      |
| 0    | 1     | 1      |
| 1    | 0     | 1      |
| 0    | 2     | 1      |
| 2    | 0     | 1      |
| 1    | 2     | 2      |
| 2    | 1     | 2      |
| 1    | 1     | 2      |
| 2    | 2     | 0      |

c++;
| left    | right   | return  |
| ------- | ------- | ------- |
| NOCOVER | NOCOVER | CAMERA  |
| NOCOVER | COVER   | CAMERA  |
| NOCOVER | CAMERA  | CAMERA  |
| COVER   | NOCOVER | CAMERA  |
| CAMERA  | NOCOVER | CAMERA  |
| COVER   | COVER   | NOCOVER |
| COVER   | CAMERA  | COVER   |
| CAMERA  | COVER   | COVER   |
| CAMERA  | NOCOVER | COVER   |
