968. Binary Tree Cameras

2023, Jun 12 2 mins read

1. Description

You are given the root 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.

2. Example

Example 1

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

Example 2

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.

3. Constraints

The number of nodes in the tree is in the range [1, 1000].
Node.val == 0

4. Solutions

Depth-First Search

n is the number of nodes in root
Time complexity: O(n)
Space complexity: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    int minCameraCover(TreeNode *root) {
        if (find_cover_(root) == 2) {
            ++result_;
        }

        return result_;
    }

private:
    int result_ = 0;

    int find_cover_(TreeNode *root) {
        // 0: there is a camera
        // 1: there is no camera but the node has been covered
        // 2: there is no camera and the node has not been covered
        if (root == nullptr) {
            // greedy, try to avoid the camera on the leaf node
            // hard to explain null node return value, so use the status rather than dp array
            return 1;
        } else {
            auto left = find_cover_(root->left);
            auto right = find_cover_(root->right);

            if (left == 2 || right == 2) {
                ++result_;
                return 0;
            } else if (left == 0 && right != 2 || left != 2 && right == 0) {
                return 1;
            } else {
                return 2;
            }
        }
    }
};