Hexo

Question

You are given the root of a binary tree. We install cameras on the tree nodes where each camera at a node can monitor its parent, itself, and its immediate children.

Return the minimum number of cameras needed to monitor all nodes of the tree.

Solution 1

贪心算法，后序遍历。每次递归根据下面两个子节点的状态来决定当前节点的状态。

每个节点一共有三种状态：

1. 未被监控，返回0。
2. 摄像头，返回1。
3. 已被监控，返回2。

递归，当当前节点为空，则返回2，表示已被监控。这样叶子节点则为未被监控的状态。

如果下面的子节点有一个未被监控，则当前节点需要设置相机，返回1，计数res+1。
如果下面的子节点有一个为摄像头，则当前节点已被监控，返回2。
否则下面的节点均为已被监控，此时返回未被监控0。

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 {
    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;   //根节点为空时返回2，这样叶子节点变为未被监控
        int left = judge(root.left);
        int right = judge(root.right);

        if(left == 0 || right == 0){    //如果左右子节点有未被监控的节点，则当前节点设置为摄像机，结果加一，返回1
            res++;
            return 1;
        }
        if(left == 1 || right == 1) return 2;    //如果左右子节点中有摄像机，则当前节点已被监控，返回2
        return 0;   //如果左右子节点都被监控，则当前节点未被监控，返回0
    }
}

Solution 2

参考：从递归优化到树形DP

树形DP。
递归，每次返回当前节点所有子节点的最小相机数。
每一个节点有三种状态：

1. 放置了相机。
2. 没有相机，但是被父节点parent监控。
3. 没有相机，但是被子节点son监控。

将三种状态分别传入minCam()方法。

递归方法 minCam()

在递归时传入两个参数hasCamera和isWatched，来判断当前节点是否有相机，是否被监控。
当当前节点为空节点时，如果设置应当有相机（做不到）则返回无限大，消除这个返回值。如果不应该有相机，则返回0。

向下递归子节点。

• 当当前节点应该有相机时：
  子节点一定被监控因此isWatched为true。
  子节点可以放置或不放置相机，因此hasCamera可以为true或false。
  注意当前位置放置相机，则子节点最多放置一个相机，因此一共有三种组合。
  由于相机至少有一个，因此返回其中的最小值+1。
• 当当前节点没有放置相机，但被父节点监控时：
  左右节点一共有四种组合，分别同时将子节点的监控状态向下递归。
  返回其中的最小值。
• 当当前节点没有放置相机，也没有被父节点监控，而是被子节点监控时：
  子节点至少有一个相机，向下递归状态，一共有三种组合。
  返回其中的最小值

然后分别调用minCam(root, true, true)和minCam(root, false, fasle)，取两者中的小值，即可得到答案。

树形dp优化剪枝

上面的方法实际采用时会超时，因为我们重复了三次调用一个子树下的三种状态的minCam。
因此我们可以将三种状态下的minCam分别保存在数组中返回。

1. withCam: 当前子树root有相机。
2. noCamWatchedByParent: 当前子树root没有相机，被父节点监控。
3. noCamWatchedBySon: 当前子树root没有相机，被子节点监控。

在每次递归时，获取数组minCam(root.left)和minCam(root.right)。
然后根据左右子节点的三个参数来计算当前节点的新的三个参数，将其返回。

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 {
    public int minCameraCover(TreeNode root) {
        return Math.min(minCam(root, true, true), minCam(root, false, false));
    }
    
    private int minCam(TreeNode root, boolean hasCamera, boolean isWatched){
        if(root == null) return hasCamera ? Integer.MAX_VALUE / 2 : 0;

        if(hasCamera){
            int min = Math.min(minCam(root.left, false, true) + minCam(root.right, false, true), minCam(root.left, true, true) + minCam(root.right, false, true));
            min = Math.min(min, minCam(root.left, false, true) + minCam(root.right, true, true));
            return 1 + min;
        }
        else if(isWatched){
            int min = Math.min(minCam(root.left, true, true) + minCam(root.right, true, true), minCam(root.left, true, true) + minCam(root.right, false, false));
            min = Math.min(min, minCam(root.left, false, false) + minCam(root.right, true, true));
            min = Math.min(min, minCam(root.left, false, false) + minCam(root.right, false, false));
            return min;
        }
        else{
            int min = Math.min(minCam(root.left, true, true) + minCam(root.right, true, true), minCam(root.left, true, true) + minCam(root.right, false, false));
            min = Math.min(min, minCam(root.left, false, false) + minCam(root.right, true, true));
            return min;
        }
    }
}

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 {
    public int minCameraCover(TreeNode root) {
        int[] res = minCam(root);
        return Math.min(res[0], res[2]);
    }
    
    private int[] minCam(TreeNode root){
        if(root == null){
            return new int[] {Integer.MAX_VALUE/2, 0, 0};
        }
        int[] left = minCam(root.left);
        int[] right = minCam(root.right);

        int withCam = 1 + Math.min(left[1] + right[1], Math.min(left[0] + right[1], left[1] + right[0]) );
        int noCamWatchedByParent = Math.min( left[0] + right[0], Math.min( left[0] + right[2], Math.min( left[2] + right[0], left[2] + right[2] )));
        int noCamWatchedBySon = Math.min( left[0] + right[0], Math.min( left[0] + right[2], left[2] + right[0]));
        return new int[] {withCam, noCamWatchedByParent, noCamWatchedBySon};
    }
}