968. 监控二叉树 二叉树+贪心

968. 监控二叉树

  1. class Solution:
  2.     def minCameraCover(self, root: Optional[TreeNode]) -> int:
  3.         def after(root):
  4.             nonlocal flag
  5.             if not root:
  6.                 return 2
  7.             l=after(root.left)
  8.             r=after(root.right)
  9.             if l==2 and r==2:
  10.                 return 0
  11.             elif l==0 or r==0:
  12.                 flag+=1
  13.                 return 1
  14.             elif l==1 or r==1:
  15.                 return 2
  16.         flag=0
  17.         if after(root)==0:
  18.             flag+=1
  19.         return flag

所以我们要从下往上看,局部最优:让叶子节点的父节点安摄像头,所用摄像头最少,整体最优:全部摄像头数量所用最少!

叶子结点返回0,叶子节点父节点应该等于1
判断 l==0 优先级大于 l==1 因为只要有一个子树没有被摄像头覆盖,l就必须成为摄像头

发表评论