莺时

东边日出西边雨,道是无晴却有晴

Open Source, Open Mind,
Open Sight, Open Future!
  menu
18 文章
3692 浏览
0 当前访客
ღゝ◡╹)ノ❤️

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

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代码

 1import scala.collection.mutable._
 2
 3/**
 4 * 描述:
 5 * ${DESCRIPTION}
 6 *
 7 * @author ludengke
 8 * @create
 9 */
10object Solution3 extends App {
11
12  var num = 0
13  def minCameraCover(root: TreeNode): Int = {
14    num = 0
15    if(dfs(root) == 0){
16      num += 1
17    }
18    num
19  }
20
21  /**
22   * 自底向上处理
23   * 0未监控,1已监控,2已设置摄像头
24   * @param root
25   * @return
26   */
27  def dfs(root: TreeNode):Int ={
28    if(root == null){
29      1
30    }else{
31      val left = dfs(root.left)
32      val right = dfs(root.right)
33      // left right 可能出现9种情况
34      if(left == 0 || right == 0){
35        num +=1
36        2
37      }else if(left == 2 || right ==2){
38        1
39      }else {
40        0
41      }
42    }
43  }
44
45  println(minCameraCover(TreeNode(1,TreeNode(2,TreeNode(3,TreeNode(4,null,TreeNode(5)),null),null),null)))
46  println(minCameraCover(TreeNode(1,TreeNode(2,TreeNode(3),TreeNode(4)),null)))
47  println(minCameraCover(TreeNode(1,TreeNode(2,TreeNode(4),TreeNode(5)),TreeNode(3,TreeNode(6),TreeNode(7)))))
48}
49
50
51

算法or数据结构

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

标题:Leetcode 每日抑题 (968. 监控二叉树)
作者:ludengke95
地址:http://xvhi.ludengke95.xyz/articles/2020/09/22/1600770849404.html