Given a binary tree, we need to install cameras on its nodes. Each camera can monitor its parent, itself, and its immediate children. The goal is to determine the minimum number of cameras reuqired to cover the entire tree.

Problem Constraints

• Number of nodes ranges from 1 to 1000.
• Node values are irrelevant (typically 0).

Core Strategy

The optimal approach uses a greedy post-order traversal. Intuitively, placing a camera on a leaf node is inefficient. It is always better to place the camera on the leaf's parent, as this covers the leaf, the parent, and potentially the other child. Therefore, leaves should remain uncovered until their parent decides to place a camera.

Node State Definition

We define three distinct states for every node during traversal:

• State 0: The node is currently uncovered (no camera and not monitored).
• State 1: The node is covered but does not have a camera.
• State 2: The node has a camera (and is obivously covered).

State Transitions

We traverse from bottom to top (post-order). For a null node (base case), we treat it as State 1. This implies that a leaf node's children are "covered," enforcing the logic that we shouldn't put a camera on the leaf itself immediately.

For a current node based on its children (l for left, r for right):

1. If either child is State 0 (uncovered), the current node must place a camera too cover that child. Result: State 2. Increment camera count.
2. If both children are State 1 (covered but no camera), the current node is not covered by anyone yet. Result: State 0.
3. If at least one child is State 2 (has a camera), that camera monitors the current node. Result: State 1.

Final Check

After the traversal, if the root node ends up as State 0 (uncovered), we need to place one additional camera on the root.

Implementation

class Solution {
    private int cameraCount;

    public int minCameraCover(TreeNode root) {
        cameraCount = 0;
        int rootState = dfsTraversal(root);
        // If root is still uncovered after traversal, add one camera
        if (rootState == 0) {
            cameraCount++;
        }
        return cameraCount;
    }

    private int dfsTraversal(TreeNode current) {
        if (current == null) {
            // Null nodes are considered "covered" to protect leaves
            return 1;
        }

        int leftChildState = dfsTraversal(current.left);
        int rightChildState = dfsTraversal(current.right);

        // Case 1: A child is uncovered, install camera here
        if (leftChildState == 0 || rightChildState == 0) {
            cameraCount++;
            return 2;
        }
        // Case 2: Both children are covered but have no cameras, current is uncovered
        else if (leftChildState == 1 && rightChildState == 1) {
            return 0;
        }
        // Case 3: At least one child has a camera, current is covered
        else {
            return 1;
        }
    }
}