LeetCode 968. 监控二叉树

题目

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

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

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

示例 1：

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

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

提示：

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

解题思路

每个节点只可能三种状态：
0-未被监控
1-摄像头
2-已被监控

代码

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */
class Solution {
    
    //全局变量 摄像头个数
    int res = 0;
    public int minCameraCover(TreeNode root) {
    
        if(judge(root) == 0)res++;
        return res;
    }
    public int judge(TreeNode root){
    
        //如果是空节点返回 已被监控
        //这样叶子节点就是 未被监控
        if(root == null)return 2;
        //根据左右孩子判断本节点属性
        int left = judge(root.left);
        int right = judge(root.right);
        //左右有一个 未被监控 则为摄像头
        if(left == 0 || right == 0){
    
            res++;
            return 1;
        }
        //左右有一个 摄像头 则为已被监控
        if(left == 1 || right == 1)return 2;
        //剩下为左右都 已被监控 则为未被监控 交给上一层节点添加摄像头
        return 0;            
    }
}

参考链接：https://leetcode.cn/problems/binary-tree-cameras/solution/tan-xin-by-lafe-d-to4v/