给定一个二叉树，我们在树的节点上安装摄像头。
节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
计算监控树的所有节点所需的最小摄像头数量。
example.png
输入：[0,0,null,0,null,0,null,null,0]
输出：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:
# 动态规划 + 广度优先搜索
def bfs(node):
# left_node中只有3种数据
# 1. node.left放监视器的最小值
# 2. node.left不放监视器被监视的最小值
# 3. node.left不放监视器不被监视的最小值
left_node = None
if not node.left is None:
left_node = bfs(node.left)
right_node = None
if not node.right is None:
right_node = bfs(node.right)
# print('left_node:', left_node)
# print('right_node:', right_node)
# 没有两个儿子的情况
if left_node is None and right_node is None:
res = [1, None, 0]
# print(res)
return res
elif left_node is None and not right_node is None:
# 放监视器的最小值，right_node怎样都行
temp1 = right_node[0]
temp1 = min(temp1, right_node[1]) if right_node[1] is not None else temp1
temp1 = min(temp1, right_node[2]) if right_node[2] is not None else temp1
temp1 += 1
# 不放监视器被监视的最小值，即right_node放
temp2 = right_node[0]
# 不放监视器不被监视的最小值
# 此时right_node必须被监视且right_node不放
temp3 = right_node[1]
res = [temp1, temp2, temp3]
# print(res)
return res
elif not left_node is None and right_node is None:
temp1 = left_node[0]
temp1 = min(temp1, left_node[1]) if left_node[1] is not None else temp1
temp1 = min(temp1, left_node[2]) if left_node[2] is not None else temp1
temp1 += 1
temp2 = left_node[0]
temp3 = left_node[1]
res = [temp1, temp2, temp3]
# print(res)
return res
# 有两个儿子的情况
# 放监视器的最小值，left_node与right_node怎样都行
min_left_node = left_node[0]
min_left_node = min(min_left_node, left_node[1]) if left_node[1] is not None else min_left_node
min_left_node = min(min_left_node, left_node[2]) if left_node[2] is not None else min_left_node
min_right_node = right_node[0]
min_right_node = min(min_right_node, right_node[1]) if right_node[1] is not None else min_right_node
min_right_node = min(min_right_node, right_node[2]) if right_node[2] is not None else min_right_node
temp1 = min_left_node + min_right_node + 1
# 不放监视器被监视的最小值，即left_node与right_node有1个放，且都得被监视
temp2 = None
# right_node且left_node放
temp2 = left_node[0] + right_node[0]
# left_node放且right_node不放被监视
if right_node[1] is not None:
temp2 = min(temp2, right_node[1] + left_node[0])
# right_node放且left_node不放被监视
if left_node[1] is not None:
temp2 = min(temp2, right_node[0] + left_node[1])
# 不放监视器不被监视的最小值
# 此时left_node、right_node必须被监视且left_node、right_node不放
temp3 = None
if left_node[1] is not None and right_node[1] is not None:
temp3 = left_node[1] + right_node[1]
res = [temp1, temp2, temp3]
# print(res)
return res
if root.left is None and root.right is None:
return 1
# print(bfs(root))
res = bfs(root)[:-1]
return min(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:
# 动态规划 + 广度优先搜索
def bfs(node):
# 有3种数据
# 1. 放监视器的最小值
# 2. 不放监视器被监视的最小值
# 3. 不放监视器不被监视的最小值
if node is None:
# 注意这儿是建立虚拟节点，为父节点服务
# 保证叶子节点和只有1个子节点的父节点计算准确。
return [float('inf'), 0, 0]
left_node = bfs(node.left)
right_node = bfs(node.right)
# 放监视器的最小值，left_node、right_node怎样都行
temp1 = min(left_node) + min(right_node) + 1
# 不放监视器被监视的最小值，即left_node与right_node至少有1个放，且不放的需要被监视
temp2 = min(left_node[0] + right_node[1], left_node[1] + right_node[0], left_node[0] + right_node[0])
# 不放监视器不被监视的最小值
# 此时left_node、right_node必须被监视且left_node、right_node不放
temp3 = left_node[1] + right_node[1]
return [temp1, temp2, temp3]
# print(bfs(root))
res = bfs(root)[:-1]
return min(res)
