监控二叉树

发表于2024-05-20更新于2024-05-20

监控二叉树

https://leetcode.cn/problems/binary-tree-cameras/description/

图 1

思路

此时这道题目还有两个难点：

  • 二叉树的遍历
    前：根左右
    中：左根右
    后：左右根
  • 如何隔两个节点放一个摄像头
    • 1、根据当前节点的左右节点的状态来确定，是否安装摄像头
      0：无覆盖
      1：有摄像头
      2：有覆盖
    • 2、具体的左右节点状态对应的行动
      1、左右节点都有一个没有覆盖：安装摄像头，result++，return 1
      2、左右节点有一个安装了摄像头，说明当前节点有覆盖，return 2
      3、左右节点都有覆盖，当前节点不安装摄像头，return 0
      4、最优如果根节点状态为0，为根节点安装摄像头。

图 2

求解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
var minCameraCover = function(root) {
  let result = 0
  //递归后序遍历
  const dfs = (node)=>{
    if(!node) return 2
    let left = dfs(node.left)
    let right = dfs(node.right)
    if(left === 0 || right === 0){
      result++
      return 1
    }
    if(left === 1 || right === 1){
      return 2
    }
    if(left === 2 && right === 2){
      return 0
    }
  }
  if(dfs(root) === 0){
    result++
  }
  return result
};