监控二叉树

发表于
本文字数： 1.4k 阅读时长 ≈ 1 分钟

LeetCode每日一题，968. Binary Tree Cameras

先看题目描述

大意就是可以在节点放相机，每个相机可以监控该节点的父节点和两个直接的子节点，给定我们一棵二叉树，问要监控整个二叉树至少需要多少个相机

算法和思路

我们定义三种状态

  • 0：节点未覆盖
  • 1：节点已覆盖但未装相机
  • 2：节点装了相机

我们用个全局变量 res 记录需要的相机数目，定义一个函数 dfs 返回值就代表节点状态，然后就开始深度优先搜索进行遍历二叉树上节点并维护 res 的值，当遍历到某个节点时，若节点为空，则直接返回 1；若节点不为空，则执行 left = dfs(root.left)，right = dfs(root.right)，得到两个直接子节点的状态，若 left 和 right 中至少有一个为 0，那么 root 必须安装相机，将 res 的值加 1，并返回 2；若 left 和 right 的值相加大于等于 3，那么就代表 root 的两个子节点均被覆盖且至少有一个安装了相机，那么 root 已被覆盖，且不需要安装相机，返回1；若 left 和 right 的值均等于 1，则代表 root 的两个子节点均被覆盖，但都未安装相机，那么 root 就未被覆盖，返回 0。深度优先搜索遍历完二叉树后返回 res 即可

注意：若最后二叉树的根节点状态值为 0，则代表根节点未被覆盖，需要将 res 值加 1，代表给根节点安装相机将其覆盖，然后再返回 res 作为最终答案

算法源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int res;

    public int minCameraCover(TreeNode root) {
        if (dfs(root) == 0) {
            res++;
        }
        return res;
    }

    // 三种状态，0 代表节点未覆盖，1代表节点已覆盖但没装相机，2代表节点已装相机
    private int dfs(TreeNode root) {
        if (root == null) return 1;
        int left = dfs(root.left);
        int right = dfs(root.right);
        if (left == 0 || right == 0) {
            res++;
            return 2;
        }
        if ((left + right) >= 3) return 1;
        if (left == 1 && right == 1) return 0;
        return -1;
    }
}