LeetCode 968. Monitor binary tree

subject

Given a binary tree , We put cameras on the nodes of the tree .

Each camera head on a node can monitor its parent object 、 Itself and its immediate children .

Calculate the minimum number of cameras required for all nodes of the monitoring tree .

Example 1：

Input ：[0,0,null,0,0]
Output ：1
explain ： As shown in the figure , One camera is enough to monitor all nodes .
Example 2：

Input ：[0,0,null,0,null,0,null,null,0]
Output ：2
explain ： You need at least two cameras to monitor all the nodes in the tree . The image above shows one of the effective locations for the camera to be placed .

Tips ：

The range of the number of nodes in a given tree is [1, 1000].
The value of each node is 0.

Their thinking

Each node can only have three states ：
0- Not monitored
1- camera
2- Monitored

Code

/** * 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 {
    
    // Global variables   Number of cameras 
    int res = 0;
    public int minCameraCover(TreeNode root) {
    
        if(judge(root) == 0)res++;
        return res;
    }
    public int judge(TreeNode root){
    
        // If it is an empty node, return   Monitored 
        // So the leaf node is   Not monitored 
        if(root == null)return 2;
        // Judge the attributes of this node according to the left and right children 
        int left = judge(root.left);
        int right = judge(root.right);
        // There is one on the left and right   Not monitored   Camera 
        if(left == 0 || right == 0){
    
            res++;
            return 1;
        }
        // There is one on the left and right   camera   Is monitored 
        if(left == 1 || right == 1)return 2;
        // The rest is left and right   Monitored   Is not monitored   Give it to the node on the upper layer to add a camera 
        return 0;            
    }
}

Reference link ：https://leetcode.cn/problems/binary-tree-cameras/solution/tan-xin-by-lafe-d-to4v/