LeetCode_110_BinaryTreeCameras

LeetCode

发布日期: 2022-06-16

更新日期: 2022-06-16

文章字数: 978

阅读时长: 3 分

阅读次数:

1. question: 监控二叉树（困难）

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/binary-tree-cameras

示例 1：

示例1

1
2
3

输入：[0,0,null,0,0]
输出：1
解释：如图所示，一台摄像头足以监控所有节点。

示例 2：

示例2

1
2
3

输入：[0,0,null,0,null,0,null,null,0]
输出：2
解释：需要至少两个摄像头来监视树的所有节点。 上图显示了摄像头放置的有效位置之一。

提示：

1 2	给定树的节点数的范围是 [1, 1000]。每个节点的值都是 0。

2. answers

这道题最开始想的是从上到下，根据层数来安装。但是显然是不对的，二叉树，每个子树都是不同的。所以这种想当然的做法是不对的。

参考题解：叶子节点不能安装摄像头，只能是其上一层。因为叶子节点占了大部分节点。

因此采用自底向上的方法，如果子节点没有摄像头或者没有被监控到，那么该节点就应该设置摄像头；如果叶子节点被覆盖了，那么此时该节点无需设置摄像头，等待父节点设置摄像头，被监控到即可。因为摄像头，存在监控范围。所以，可以设置叶子节点的状态：

节点无覆盖（0）
节点有覆盖（1）
节点有摄像头（2）

注意，节点无摄像头，即意味着节点有覆盖或者无覆盖。因为一般情况下，节点存在两个孩子节点，因此父节点根据两个子节点的状态来设置自己的状态（三个状态）。两个孩子的状态共有8种。可分为三类：

至少有一个没有覆盖（00,01,10,02,20）
均覆盖（11）
至少有一个摄像头（12,21,22）（注意，没有覆盖的优先级大于有摄像头）

对于本节点的状态，可根据下面设置：

如果一个节点的两个孩子至少有一个是无覆盖的，那么本节点必须安装摄像头。（否则，该节点是无法覆盖的，因为是自底向上，所以该节点既然无覆盖，只能是本节点覆盖）
如果一个节点的两个孩子均是有覆盖，那么本节点无需安装摄像头，状态为无覆盖。
如果一个节点的两个孩子至少有一个是有摄像头，那么本节点肯定可以覆盖到，状态为有覆盖。

为了更方便地递归，对于叶子节点，设置为无覆盖（为了保证一致性，对于null节点，设置为有覆盖，这样叶子节点满足了上面第二个要求；并且对于树中只有一个子节点的节点，也可以保证不影响到该节点）。

代码如下所示：

public class Solution_0110_02 {

    public int res;

    public int dfs(TreeNode root) {

        if(root == null) return 1;

        int left = dfs(root.left);
        int right = dfs(root.right);

        // 至少有一个是无覆盖：00 01 10 02 20
        if(left == 0 || right == 0) {
            res ++;
            return 2;
        }

        // 均是有覆盖：11
        if(left == 1 && right == 1) return 0;

        // 至少有一个有摄像头:21 12 22
        else return 1;

    }

    public int minCameraCover(TreeNode root) {

        // 注意根节点
        return dfs(root) == 0 ? res += 1 : res;
    }

    public static void main(String[] args) {


        TreeNode tn5 = new TreeNode(0);
        TreeNode tn4 = new TreeNode(0, null, tn5);
        TreeNode tn3 = new TreeNode(0, tn4, null);
        TreeNode tn2 = new TreeNode(0, tn3, null);
        TreeNode tn1 = new TreeNode(0, tn2, null);

        Solution_0110_02 s = new Solution_0110_02();

        System.out.println(s.minCameraCover(tn1));


    }
}