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

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

题目链接

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

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

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

解题思路

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

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

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

• 递归到 null 节点时的状态,坑了我好大一把 , 咱们的目的是让叶子节点的状态为 0,触发自下向上的处理,按照下表叶子节点为根,null 节点为子节点,符合(1,1)状态的导出结果,所以递归到 null 的时候需要返回 1.
• 递归完成后,如果根节点状态为 0,表示没有监控,则需要在根节点设置摄像机

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. 递归 , 递归 , 递归 , (自下向上)