# 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

# 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++

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 |