968. Binary Tree Cameras

Problem 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.

Example 1:

Input: root = [0,0,null,0,0]
Output: 1
Explanation: One camera is sufficient 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.

Constraints:

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

Python Solution

class Solution:
    def minCameraCover(self, root: TreeNode) -> int:
        self.ans = 0
        
        def dfs(node: TreeNode) -> int:
            if not node:
                return 0
                
            left = dfs(node.left)
            right = dfs(node.right)
            
            if left == 0 and right == 0:
                return 1
            elif left == 1 or right == 1:
                self.ans += 1
                return 2
            else:
                return 0
                
        return self.ans + (1 if dfs(root) == 1 else 0)

Java Solution

class Solution {
    private int ans = 0;
    
    public int minCameraCover(TreeNode root) {
        return (dfs(root) == 1 ? 1 : 0) + ans;
    }
    
    private int dfs(TreeNode node) {
        if (node == null) {
            return 0;
        }
        
        int left = dfs(node.left);
        int right = dfs(node.right);
        
        if (left == 0 && right == 0) {
            return 1;
        } else if (left == 1 || right == 1) {
            ans++;
            return 2;
        } else {
            return 0;
        }
    }
}

C++ Solution

class Solution {
private:
    int ans = 0;
    
    int dfs(TreeNode* node) {
        if (!node) {
            return 0;
        }
        
        int left = dfs(node->left);
        int right = dfs(node->right);
        
        if (left == 0 && right == 0) {
            return 1;
        } else if (left == 1 || right == 1) {
            ans++;
            return 2;
        } else {
            return 0;
        }
    }
    
public:
    int minCameraCover(TreeNode* root) {
        return (dfs(root) == 1 ? 1 : 0) + ans;
    }
};

JavaScript Solution

/**
 * @param {TreeNode} root
 * @return {number}
 */
var minCameraCover = function(root) {
    let ans = 0;
    
    function dfs(node) {
        if (!node) {
            return 0;
        }
        
        const left = dfs(node.left);
        const right = dfs(node.right);
        
        if (left === 0 && right === 0) {
            return 1;
        } else if (left === 1 || right === 1) {
            ans++;
            return 2;
        } else {
            return 0;
        }
    }
    
    return (dfs(root) === 1 ? 1 : 0) + ans;
};

C# Solution

public class Solution {
    private int ans = 0;
    
    public int MinCameraCover(TreeNode root) {
        return (Dfs(root) == 1 ? 1 : 0) + ans;
    }
    
    private int Dfs(TreeNode node) {
        if (node == null) {
            return 0;
        }
        
        int left = Dfs(node.left);
        int right = Dfs(node.right);
        
        if (left == 0 && right == 0) {
            return 1;
        } else if (left == 1 || right == 1) {
            ans++;
            return 2;
        } else {
            return 0;
        }
    }
}