- class Solution:
- def minCameraCover(self, root: Optional[TreeNode]) -> int:
- def after(root):
- nonlocal flag
- if not root:
- return 2
- l=after(root.left)
- r=after(root.right)
- if l==2 and r==2:
- return 0
- elif l==0 or r==0:
- flag+=1
- return 1
- elif l==1 or r==1:
- return 2
- flag=0
- if after(root)==0:
- flag+=1
- return flag
所以我们要从下往上看,局部最优:让叶子节点的父节点安摄像头,所用摄像头最少,整体最优:全部摄像头数量所用最少!
叶子结点返回0,叶子节点父节点应该等于1
判断 l==0 优先级大于 l==1 因为只要有一个子树没有被摄像头覆盖,l就必须成为摄像头