Given a binary tree, we install cameras on the nodes of the tree. 
Each camera at a node can monitor its parent, itself, and its immediate children.
Calculate the minimum number of cameras needed to monitor all nodes of the tree.
 
Example 1:


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


Example 2:

Input: [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.


Note:

The number of nodes in the given tree will be in the range [1, 1000].
Every node has value 0.

Difficulty: interview

Starter code:

# 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: TreeNode) -> int:
        

Solutions:
# 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: TreeNode) -> int:
        
        def dfs(node):
            if not node:
                return 2
            left = dfs(node.left)
            right = dfs(node.right)
            
            if left == 0 or right == 0:
                self.res += 1
                return 1
            if left == 1 or right == 1:
                return 2
            else:
                return 0
            
        self.res = 0
        return (dfs(root) == 0) + self.res



class Solution:
    def minCameraCover(self, root):
        self._res = 0
        if self._dfs(root) == 0:
            self._res += 1
        return self._res
    
    # 0表示这个点没有被cover
    # 1表示这个点被cover了，但是没有camera
    # 2表示这个点有camera
    def _dfs(self, node):
        # 空点我们也认为被cover了
        # 但是没有camera
        if not node:
            return 1
        
        left = self._dfs(node.left)
        right = self._dfs(node.right)
        
        # 如果左节点或者右节点中有cover不住的
        # 需要在node上加camera了
        if left == 0 or right == 0:
            self._res += 1
            return 2
        elif left == 2 or right == 2:
            return 1
        # 此时左节点和右节点肯定都是1
        # 表示左右孩子都被cover住了
        # 我们直接退出，在主函数里面处理这个node就好了
        else:
            return 0

# 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: TreeNode) -> int:
        dump1={}
        
        dump2={}
        
        def f(root):
            if root==None:
                return 0
            if root in dump1:
                return dump1[root]
            ans=1+min(f(root.left), g(root.left, True))+min(f(root.right), g(root.right, True))
            dump1[root]=ans
            return ans
        
        def g(root, covered):
            if root==None:
                return 0
            if (root, covered) in dump2:
                return dump2[(root, covered)]
            if root.left==None and root.right==None:
                if covered:
                    return 0
                return float('inf')
            ans=float('inf')
            if not covered:
                if root.left!=None:
                    ans=f(root.left)+min(g(root.right, False), f(root.right))
                if root.right!=None:
                    ans=min(ans, f(root.right)+min(f(root.left), g(root.left, False)))
            else:
                ans=min(f(root.left), g(root.left, False))+min(f(root.right), g(root.right, False))
            dump2[(root, covered)]=ans
            return ans
        
        if root.left==None and root.right==None:
            return 1
        
        return min(f(root), g(root, False))


# 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: TreeNode) -> int:
        if not root: 
            return 0
        
        def solve(node):
            if not node: return 0,0,float('inf')
            L = solve(node.left)
            R = solve(node.right)
            
            dp0 = L[1] + R[1]
            
            dp1 = min(L[2] + min(R[1:]), R[2] + min(L[1:]))
            dp2 = 1 + min(L) + min(R)
            
            return dp0, dp1, dp2
        print(solve(root))
        return min(solve(root)[1:])

# 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:
    
    @lru_cache(None)
    def helper(self, node, covered, camera):
        if(node == None):
            return 0  
        if(camera):
            return 1+self.helper(node.left,True,False)+self.helper(node.right, True, False)
        if(covered):
            cam_on = 1+self.helper(node.left,True,False)+self.helper(node.right, True, False)
            cam_off = self.helper(node.left,False,False)+self.helper(node.right, False, False)
            return min(cam_on, cam_off)
        
        #Not covered
        cam_on = 1+self.helper(node.left,True,False)+self.helper(node.right, True, False)
        cam_on_left = self.helper(node.left,False, True)+self.helper(node.right, False, False) if node.left != None else inf
        cam_on_right = self.helper(node.left, False, False)+self.helper(node.right, False, True) if node.right != None else inf
        
        return min(cam_on, cam_on_left, cam_on_right)
    
    def minCameraCover(self, root: TreeNode) -> int:
        return min(self.helper(root, False, True), self.helper(root, False, False))

class Solution:
    def minCameraCover(self, root: TreeNode) -> int:
        self.search(root)
        return root.min        
    
    def search(self, node):
        if node.left:
            self.search(node.left)
            if node.right:
                self.search(node.right)
                node.min_with = 1 + node.left.min_bottom + node.right.min_bottom
                node.min_bottom = min(node.min_with, node.left.min + node.right.min)
                node.min = min(node.min_with, node.left.min_with+node.right.min,
                              node.left.min+node.right.min_with)
            else:
                node.min_bottom = node.left.min
                node.min_with = 1 + node.left.min_bottom
                node.min = min(node.min_with, node.left.min_with)
        else:
            if node.right:
                self.search(node.right)
                node.min_bottom = node.right.min
                node.min_with = 1 + node.right.min_bottom
                node.min = min(node.min_with, node.right.min_with)
            else:
                node.min_bottom = 0
                node.min_with = 1
                node.min = 1

# 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: TreeNode) -> int:
        \"\"\"
        #对于每个节点root，需要维护三种类型的状态：
        1. 状态a: root必须放置摄像头的情况下，覆盖整棵树需要的摄像头数目
        2. 状态b: 覆盖整棵树需要的摄像头数目，无论root是否放置摄像头。
        3. 状态c: 覆盖两颗子树需要的摄像头数目，无论节点root本身是否被监控到。

        \"\"\"
        def dfs(root):
            if not root:
                return [float('inf'), 0, 0]
            
            la, lb, lc = dfs(root.left)
            ra, rb, rc = dfs(root.right)
            a = lc + rc +1
            b = min(a, la+rb, ra+lb)
            c = min(a, lb+rb)
            return [a, b, c]
        a, b, c = dfs(root)
        return b
        

# 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: TreeNode) -> int:
        # three cases for a node (root), DP: up -> bottom
        # 0: root is not covered, all nodes below are covered
        # 1: root is covered, all nodes below are covered, root has no camera
        # 2: root is covered, all nodes below are covered, root has a camera
        
        # 0: L, R children both in case 1
        # 1: L, R can be 1 or 2, at least one child is in case 2
        # 2: L, R children can be any case
        
        def dp(node):
            if not node:
                return [0, 0, float(inf)]
            
            L = dp(node.left)
            R = dp(node.right)
            dp0 = L[1] + R[1]
            dp1 = min(L[2] + min(R[1:]), min(L[1:]) + R[2])
            dp2 = 1 + min(L) + min(R)
            return [dp0, dp1, dp2]
        return min(dp(root)[1:])
            


# 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: TreeNode) -> int:
        nothing =0
        leaf =1
        has = 2
        covered = 3
        coverme = 4
        self.ans =0
        
        def rec(root):
            if not root:
                return 0
            if not root.left and not root.right:
                
                return leaf
            left = rec(root.left)
            right = rec(root.right)
            
            if left == leaf or right == leaf or left == coverme or right == coverme:
                self.ans +=1
                return has
            if left == has or right == has:
                return covered
            return coverme
        r = rec(root)
        if r == leaf or r == coverme:
            self.ans += 1
        return self.ans


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def minCameraCover(self, root: TreeNode) -> int:
        # self.times = 0
        self.DP = dict()
        def dp(node,flag):
            if (node, flag) in self.DP:
                return self.DP[(node, flag)]
            # self.times += 1
            # print(self.times)
            if flag == 0 and node is None:
                result = 1
            elif node is None:
                result = 0
            elif flag == 2:#satisfied
                result = min(dp(node.left,1) + dp(node.right,1), dp(node.left,2) + dp(node.right,2)+1)
            elif flag == 1:#self or descend should be
                a = dp(node.left,0)
                b = dp(node.right,1)
                aa = dp(node.left,1)
                bb = dp(node.right,0)
                result = min(a + b, aa+bb, a+bb, dp(node.left,2) + dp(node.right,2) + 1)
            else:
                result = dp(node.left,2) + dp(node.right,2) + 1
            self.DP[(node, flag)] = result
            return result
        return min(dp(root,0), dp(root,1))

# 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: TreeNode) -> int:
        # print('gg')
        def do(node):
            if not node:
                return
            dummy = TreeNode()
            dummy.use = 0
            dummy.covered = dummy.notcovered = 99999
            
            node.use = 1
            node.covered = 0
            node.notcovered = 0
            
            do(node.left)
            do(node.right)
            l = node.left
            r = node.right
            
            ml = min(l.use, l.covered, l.notcovered) if l else 9999
            mr = min(r.use, r.covered, r.notcovered) if r else 9999
            node.use = 1 + (ml if node.left else 0) + (mr if node.right else 0)
            node.covered = min((l.covered if l else 0) + (r.use if r else 9999), (l.use if l else 9999) + (r.covered if r else 0), (l.use if l else 9999) + (r.use if r else 9999))
            node.notcovered = (l.covered if l else 0) + (r.covered if r else 0)
            # print(node.use, node.covered, node.notcovered)

        do(root)
        return 0 if not root else min(root.use, root.covered)


# 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: TreeNode) -> int:
        ans = 0
        def recursive(root):
            nonlocal ans
            if not root.left and not root.right:
                return 0, 0
            left_cover = 1
            right_cover= 1
            left_camera = 0
            right_camera  = 0
            if root.left:
                left_cover, left_camera = recursive(root.left)
            if root.right:
                right_cover, right_camera = recursive(root.right)
            if not (left_cover and right_cover):
                ans +=1
                return 1, 1
            elif left_camera or right_camera:
                return 1, 0
            else:
                return 0, 0
        return ans if recursive(root)[0] else ans+1
                


# 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: TreeNode) -> int:
        def solve(node):
            if node is None:
                return 0, 0, 1000
            l = solve(node.left)
            r = solve(node.right)
            
            dp0 = l[1] + r[1]
            dp1 = min(l[2] + min(r[1:]), min(l[1:]) + r[2])
            dp2 = 1 + min(l) + min(r)
            
            return dp0, dp1, dp2
        return min(solve(root)[1:])

# 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: TreeNode) -> int:
        
        @lru_cache(None)
        def cal(root, st):
            if root:
                if st == 1:
                    return min(cal(root.left, 2)+cal(root.right, 2),
                              1 + cal(root.left, 1) + cal(root.right, 1))
                elif st == 2:
                    if root.left == root.right == None:
                        return 1
                    if root.left and root.right:                        
                        return min(cal(root.left, 3)+cal(root.right, 2),
                                    cal(root.left, 2)+cal(root.right, 3),
                                    1 + cal(root.left, 1) + cal(root.right, 1))
                    else:
                         return min(cal(root.left, 3)+cal(root.right, 3),
                                    cal(root.left, 3)+cal(root.right, 3),
                                    1 + cal(root.left, 1) + cal(root.right, 1))
                        
                elif st == 3:
                    return 1 + cal(root.left, 1) + cal(root.right, 1)
            else:
                return 0
            
        return cal(root, 2)

# 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: TreeNode) -> int:
        # 1 means monitored, 2 means camera
        if root.left is None and root.right is None:
            return 1
        
        self.ans = 0
        # with dp?
        def dfs(t, pre=None):
            if t is None:
                return 0
            t.pre = pre
            # idea: put a camera above each leaf, mark around that we are ok, then cut those nodes from the tree
            # so that when we go up in the recursion there are new leaves
            dfs(t.left, t)
            dfs(t.right, t)
            
            if (not t.left or t.left.val < 0) and (not t.right or t.right.val < 0) and t.val == 0:
                if pre and pre.val != -2:
                    pre.val = -2
                    self.ans += 1
                    if pre.pre:
                        pre.pre.val = -1 # val of -1 means cut
                if not pre and t.val == 0:
                    self.ans += 1
                    t.val = -1
                
        dfs(root)
        print(root)
        return self.ans
                
                
        # min num of camera left
            
            


# 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


# Intuition:
# Consider a node in the tree.
# It can be covered by its parent, itself, its two children.
# Four options.

# Consider the root of the tree.
# It can be covered by left child, or right child, or itself.
# Three options.

# Consider one leaf of the tree.
# It can be covered by its parent or by itself.
# Two options.

# If we set a camera at the leaf, the camera can cover the leaf and its parent.
# If we set a camera at its parent, the camera can cover the leaf, its parent and its sibling.

# We can see that the second plan is always better than the first.
# Now we have only one option, set up camera to all leaves' parent.

# Here is our greedy solution:

# Set cameras on all leaves' parents, then remove all covered nodes.
# Repeat step 1 until all nodes are covered.
# Explanation:
# Apply a recusion function dfs.
# Return 0 if it's a leaf.（need to be covered0
# Return 1 if it's a parent of a leaf, with a camera on this node.
# Return 2 if it's coverd, without a camera on this node.

# For each node,
# if it has a child, which is leaf (node 0), then it needs camera.
# if it has a child, which is the parent of a leaf (node 1), then it's covered.

# If it needs camera, then res++ and we return 1.
# If it's covered, we return 2.
# Otherwise, we return 0.


class Solution:
    def minCameraCover(self, root):
        self.res = 0
        def dfs(root):
            if not root: return 2
            l, r = dfs(root.left), dfs(root.right)
            if l == 0 or r == 0:
                self.res += 1   #在里面改变, 需要防止一个节点
                return 1  #这个点return 1 代表放了camera了
            elif l == 1 or r == 1:
                return 2
            elif l == 2 or r == 2:
                return 0
        return (dfs(root) == 0) + self.res




# 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 helper(self, root):
        if not root:
            return 2
            
        left = self.helper(root.left)
        right = self.helper(root.right)
        
        if left == 0 or right == 0:
            self.count+=1
            return 1
        if left == 1 or right == 1:
            return 2  
        else:
            return 0
        
            
    def minCameraCover(self, root: TreeNode) -> int: 
        
        self.count = 0
        return (self.helper(root)==0) + self.count

# 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


# Intuition:
# Consider a node in the tree.
# It can be covered by its parent, itself, its two children.
# Four options.

# Consider the root of the tree.
# It can be covered by left child, or right child, or itself.
# Three options.

# Consider one leaf of the tree.
# It can be covered by its parent or by itself.
# Two options.

# If we set a camera at the leaf, the camera can cover the leaf and its parent.
# If we set a camera at its parent, the camera can cover the leaf, its parent and its sibling.

# We can see that the second plan is always better than the first.
# Now we have only one option, set up camera to all leaves' parent.

# Here is our greedy solution:

# Set cameras on all leaves' parents, then remove all covered nodes.
# Repeat step 1 until all nodes are covered.
# Explanation:
# Apply a recusion function dfs.
# Return 0 if it's a leaf.
# Return 1 if it's a parent of a leaf, with a camera on this node.
# Return 2 if it's coverd, without a camera on this node.

# For each node,
# if it has a child, which is leaf (node 0), then it needs camera.
# if it has a child, which is the parent of a leaf (node 1), then it's covered.

# If it needs camera, then res++ and we return 1.
# If it's covered, we return 2.
# Otherwise, we return 0.


class Solution:
    def minCameraCover(self, root):
        self.res = 0
        def dfs(root):
            if not root: return 2
            l, r = dfs(root.left), dfs(root.right)
            if l == 0 or r == 0:
                self.res += 1   #在里面改变
                return 1
            return 2 if l == 1 or r == 1 else 0
        return (dfs(root) == 0) + self.res




# 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: TreeNode) -> int:
        covered = {None}
        self.ans = 0
        
        def dfs(node, par):
            
            if node:
                dfs(node.left, node)
                dfs(node.right, node)

                if (par is None and node not in covered) or node.left not in covered or node.right not in covered :
                    covered.update({node, par, node.right, node.left})
                    self.ans += 1
                
        dfs(root, None)
        return self.ans

class Solution:
    def minCameraCover(self, root):
        def solve(node):
            # 0: Strict ST; All nodes below this are covered, but not this one
            # 1: Normal ST; All nodes below and incl this are covered - no camera
            # 2: Placed camera; All nodes below this are covered, plus camera here

            if not node: return 0, 0, float('inf')
            L, R = solve(node.left), solve(node.right)
            dp0 = L[1] + R[1]
            dp1 = min(L[2] + min(R[1:]), R[2] + min(L[1:]))
            dp2 = 1 + min(L) + min(R)
            return dp0, dp1, dp2

        return min(solve(root)[1:])

# 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: TreeNode) -> int:
        
        
        def dfs(node):
            nonlocal cnt
            
            if node:
                left = dfs(node.left)
                right = dfs(node.right)
                
                if not left or not right:
                    cnt += 1
                    return 2
                elif left == 2 or right == 2:
                    return 1
                else:
                    return 0
            else:
                return 1
        
        cnt = 0
        
        if not dfs(root):
            return cnt + 1
        else:
            return cnt
        
        
        


# 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: TreeNode) -> int:
        if not root:
            return 0
        seen = set()
        self.ans = 0
        def inorder(root,parent=None):
            if root:
                inorder(root.left,root)
                inorder(root.right,root)
                for i in [parent,root,root.left,root.right]:
                    if i and i in seen:
                        break
                else:
                    self.ans+=1
                    seen.update(set([parent,root,root.left,root.right]))
        inorder(root)
        return self.ans