1. 监控二叉树 - Binary Tree Cameras

[DFS] [动态规划]

Problem Link

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

Example:

示例 1:

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

solution

My solution

 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
34
35
36
37
38
39
40
41
/**
 * 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

 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
34
35
36
/**
 * 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中每个节点的染色(白、黄、红)