You've successfully subscribed to The Daily Awesome
Great! Next, complete checkout for full access to The Daily Awesome
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.
Success! Your billing info is updated.
Billing info update failed.

968. 监控二叉树 - Binary Tree Cameras

. 2 min read

[DFS] [动态规划]

给定一个二叉树,我们在树的节点上安装摄像头。
节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
计算监控树的所有节点所需的最小摄像头数量。

Example:

示例 1:

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

solution

My solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private int num_Camera = 0;

    public int minCameraCover(TreeNode root) {
        num_Camera = 0;
        if(root == null)
            return 0;
        if(dfs(root) == 2)
            num_Camera++;
        return num_Camera;
    }
    /*
    0:  该节点已经安装了监视器
    1:  该节点被监视,没有安装监视器
    2: 该节点未被监视,没有安装监视器 -> 它的上一级需要安装监视器
    */
    private int dfs(TreeNode node) {
        if (node == null)
            return 1; 
        int left = dfs(node.left);
        int right = dfs(node.right);
        /* 左右节点有一个安装监视器即可 */
        if (left == 2 || right == 2) {
            num_Camera++;
            return 0;
        } else if (left == 0 || right == 0)           
            return 1;
        else 
            return 2;
    }
}

复杂度分析 O(|V|)

Other Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int minCameraCover(TreeNode root) {
        int count = order(root);
        if(root==null)
            return 0;
        if(root.val==0)
            count++;
        return count;
        
    }
    private int order(TreeNode root){
        if(root==null)
            return 0;
        int count =0;
        count = order(root.left)+order(root.right);
        if((root.left!=null&&root.left.val==0)||(root.right!=null&&root.right.val==0)){
            root.val=2;
            count++;
            return count;
        }
        if((root.left!=null&&root.left.val==2)||(root.right!=null&&root.right.val==2)){
            root.val=1;
        }
        return count;
    }
}

复杂度分析

Notes

关键在于合理地给每一个节点表明状态。

类似于DFS中每个节点的染色(白、黄、红)