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.

Source: leetcode | Difficulty: MEDIUM
Tags: Tree algorithms

Dynamic programming

Graph traversal

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:
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

	def _dfs(self, node):
		if not node:
			return 1
		left = self._dfs(node.left)
		right = self._dfs(node.right)
		if left == 0 or right == 0:
			self._res += 1
			return 2
		elif left == 2 or right == 2:
			return 1
		else:
			return 0


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))


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:])


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)
		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)
		elif 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


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


class Solution:

	def minCameraCover(self, root: TreeNode) -> int:
		self.DP = dict()

		def dp(node, flag):
			if (node, flag) in self.DP:
				return self.DP[node, flag]
			if flag == 0 and node is None:
				result = 1
			elif node is None:
				result = 0
			elif flag == 2:
				result = min(dp(node.left, 1) + dp(node.right, 1), dp(node.left, 2) + dp(node.right, 2) + 1)
			elif flag == 1:
				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))


class Solution:

	def minCameraCover(self, root: TreeNode) -> int:

		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)
		do(root)
		return 0 if not root else min(root.use, root.covered)


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


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:])


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)


class Solution:

	def minCameraCover(self, root: TreeNode) -> int:
		if root.left is None and root.right is None:
			return 1
		self.ans = 0

		def dfs(t, pre=None):
			if t is None:
				return 0
			t.pre = pre
			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
				if not pre and t.val == 0:
					self.ans += 1
					t.val = -1
		dfs(root)
		print(root)
		return self.ans


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
			elif l == 1 or r == 1:
				return 2
			elif l == 2 or r == 2:
				return 0
		return (dfs(root) == 0) + self.res


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


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: 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


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