Leetcode 每日抑题 (968. 监控二叉树)

本贴最后更新于 1283 天前,其中的信息可能已经时移世易

LeetCode 的每日抑题系列 , LeetCode 会每天随机一道题作为签到题.我也是菜鸡,如果今天没 A 掉,那只能证明我离大神又进了一步.

题目链接

题名 通过率 难度
968. 监控二叉树 47.1% 困难

给定一个二叉树,我们在树的节点上安装摄像头。

节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。

计算监控树的所有节点所需的最小摄像头数量。

解题思路

  1. 今天尴尬的恨不得用脚趾在地上抠出一个三室一厅 , 因为 null 节点返回值的问题困了好久; 自上向下耗费了 n 久的时间,最后还是放弃,使用了自下向上
  2. dfs 自下向上按照最优化设置监控就完事了,最后返回设置监控的数量

节点有三种状态: 无监控(0) , 有监控(1,有摄像机的上下一层) , 有摄像机(2).

最终目的是使得整个树都从 0 状态变到 1 或 2 状态.按照最优化的思想根据子节点状态设置父节点状态.

  • 递归到 null 节点时的状态,坑了我好大一把 , 咱们的目的是让叶子节点的状态为 0,触发自下向上的处理,按照下表叶子节点为根,null 节点为子节点,符合(1,1)状态的导出结果,所以递归到 null 的时候需要返回 1.
  • 递归完成后,如果根节点状态为 0,表示没有监控,则需要在根节点设置摄像机
左节点状态 右节点状态 父节点状态(根据前两个推出来的) 备注
0 0 2 左右节点都无监控,需要父节点安装监控
0 1 2 左右节点仅有一个节点无监控,需要父节点安装摄像机(最优化的思想 在父节点安装摄像机比在子节点辐射范围更大)
0 2 2 同上
1 0 2 同上
1 1 0 左右都是监控,按照最优化思想父节点的监控任务可以交给祖父节点(给父节点和子节点都会造成冗余)
1 2 1 左右节点至少一个节点安装摄像机,父节点处于可监控状态
2 0 2 同 0,2 状态
2 1 1 同 1,2 状态
2 2 1 同 1,2 状态

scala 代码

import scala.collection.mutable._

/**
 * 描述:
 * ${DESCRIPTION}
 *
 * @author ludengke
 * @create
 */
object Solution3 extends App {

  var num = 0
  def minCameraCover(root: TreeNode): Int = {
    num = 0
    if(dfs(root) == 0){
      num += 1
    }
    num
  }

  /**
   * 自底向上处理
   * 0未监控,1已监控,2已设置摄像头
   * @param root
   * @return
   */
  def dfs(root: TreeNode):Int ={
    if(root == null){
      1
    }else{
      val left = dfs(root.left)
      val right = dfs(root.right)
      // left right 可能出现9种情况
      if(left == 0 || right == 0){
        num +=1
        2
      }else if(left == 2 || right ==2){
        1
      }else {
        0
      }
    }
  }

  println(minCameraCover(TreeNode(1,TreeNode(2,TreeNode(3,TreeNode(4,null,TreeNode(5)),null),null),null)))
  println(minCameraCover(TreeNode(1,TreeNode(2,TreeNode(3),TreeNode(4)),null)))
  println(minCameraCover(TreeNode(1,TreeNode(2,TreeNode(4),TreeNode(5)),TreeNode(3,TreeNode(6),TreeNode(7)))))
}



算法 or 数据结构

  1. 递归 , 递归 , 递归 , (自下向上)
  • LeetCode

    LeetCode(力扣)是一个全球极客挚爱的高质量技术成长平台,想要学习和提升专业能力从这里开始,充足技术干货等你来啃,轻松拿下 Dream Offer!

    209 引用 • 72 回帖
  • 每日抑题
    6 引用 • 3 回帖
  • DFS
    1 引用
  • 递归
    15 引用 • 9 回帖

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...