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.

&nbsp;
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.


&nbsp;
Constraints:


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


import itertools
# 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 minCameraHelper(self, root: Optional[TreeNode]) -> (int, int):
        # Return 3 things:
        # cam, uncam, uncov
        # cam(era) is best score for valid tree with camera at root
        # uncam(era) is best score for valid tree without camera at root
        # uncov(ered) is best score for invalid tree, where the only invalidity (i.e. the only uncovered node) is the root node
        
        # Note: maxint (float("inf")) is used to signify situations that don't make sense or can't happen.
        # Anywhere there is a float("inf"), you can safely replace that with a 1 as 1 is as bad or worse than worst practical,
        # but I stick with maxint to highlight the nonsensical cases for the reader!
        
        if not root.left and not root.right:
            # base case: leaf
            # Note: "Uncam" setting doesn't make much sense (a leaf with no parents can either have a camera or be uncovered,
            #       but not covered with no camera)
            return 1, float("inf"), 0
        
        if root.left:
            left_cam, left_uncam, left_uncov = self.minCameraHelper(root.left)
        else:
            # base case: empty child
            # Need to prevent null nodes from providing coverage to parent, so set that cost to inf
            left_cam, left_uncam, left_uncov = float("inf"), 0, 0
            
        if root.right:
            right_cam, right_uncam, right_uncov = self.minCameraHelper(root.right)
        else:
            # base case: empty child
            # Need to prevent null nodes from providing coverage to parent, so set that cost to inf
            right_cam, right_uncam, right_uncov = float("inf"), 0, 0
            
        # Get the possible combinations for each setting    
        cam_poss = itertools.product([left_cam, left_uncam, left_uncov], [right_cam, right_uncam, right_uncov])
        uncam_poss = [(left_cam, right_cam), (left_uncam, right_cam), (left_cam, right_uncam)]
        uncov_poss = [(left_uncam, right_uncam)]
        
        # Compute costs for each setting
        cam = min([x + y for x, y in cam_poss]) + 1
        uncam = min([x + y for x, y in uncam_poss])
        uncov = min([x + y for x, y in uncov_poss])
        
        return cam, uncam, uncov
                    
    def minCameraCover(self, root: Optional[TreeNode]) -> int:
        cam, uncam, _ = self.minCameraHelper(root)
        return min(cam, uncam)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private int count = 0;
    public int minCameraCover(TreeNode root) {
        if(helper(root) == -1)
            count++;
        return count;
    }
    
    //post order
    //0 - have camera
    //1 - covered
    //-1 - not covered
    public int helper(TreeNode root) {
        if(root == null)
            return 1;
        int left = helper(root.left);
        int right = helper(root.right);
        if(left == -1 || right == -1) {
            count++;
            return 0;
        }
        if(left == 0 || right == 0)
            return 1;
        
        return -1;
    }
}
class Solution {
public:
    map<TreeNode*, int> mpr;
    int dp[1009][3];
    int minCameraCover(TreeNode* root)
    {
        int num = 0;
        adres(root, num);
        memset(dp, -1, sizeof(dp));

        int t1 = dp_fun(root, 0), t2 = dp_fun(root, 1), t3 = dp_fun(root, 2);

        return min({t1, t3});

    }

    int dp_fun(TreeNode* cur, int st)
    {
        int nd = mpr[cur];
        if(dp[nd][st] == -1)
        {
            if(cur == NULL)
            {
                if(st == 2)
                {
                    return 1e8;
                }
                else
                {
                    return 0;
                }
            }
            if(st == 2)
            {
                dp[nd][st] = 1 + min({dp_fun(cur->left, 1) + dp_fun(cur->right, 1), dp_fun(cur->left, 1) + dp_fun(cur->right, 2), dp_fun(cur->left, 2) + dp_fun(cur->right, 1), dp_fun(cur->left, 2) + dp_fun(cur->right, 2)});
            }
            else if(st == 1)
            {
                dp[nd][st] = min({dp_fun(cur->left, 0) + dp_fun(cur->right, 0), dp_fun(cur->left, 0) + dp_fun(cur->right, 2), dp_fun(cur->left, 2) + dp_fun(cur->right, 0), dp_fun(cur->left, 2) + dp_fun(cur->right, 2)});
            }
            else
            {
                dp[nd][st] = min({dp_fun(cur, 2), dp_fun(cur->left, 2) + dp_fun(cur->right, 0), dp_fun(cur->left, 0) + dp_fun(cur->right, 2), dp_fun(cur->left, 2) + dp_fun(cur->right, 2)});
            }
        }
        return dp[nd][st];
    }

    void adres(TreeNode* cur, int &cnt)
    {
        if(cur == NULL)
        {
            return;
        }
        mpr[cur] = cnt;
        cnt++;

        adres(cur->left, cnt);
        adres(cur->right, cnt);
    }
};
var minCameraCover = function(root) {
    let cam = 0;
    // 0 --> No covered
    // 1 --> covered by camera
    // 2 --> has camera
    function dfs(root) {
        if(root === null) return 1;

        const left = dfs(root.left);
        const right = dfs(root.right);

        if(left === 0 || right === 0) { // child required a camera to covered
            cam++;
            return 2;
        } else if(left === 2 || right === 2) { // child has camera so i am covered
            return 1;
        } else { // child is covered but don't have camera,So i want camera
            return 0;
        }
    }

    const ans = dfs(root);

    if(ans === 0) ++cam;

    return cam;
};
Binary Tree Cameras