leetcode

LeetCode 968. Binary Tree Cameras

Problem

LeetCode 968. Binary Tree Cameras

1. 题目简述

给出一棵二叉树，我们向节点中加入camera，每个节点可以监控其父节点和左右孩子，求最少需要多少个camera才能监控整棵树（节点不大于1000个，每个节点的value都是0）。例如：

最少camera数
Input: [0,0,null,0,null,0,null,null,0]
Output: 2
Explanation: At least two cameras are needed to monitor all nodes of the tree. The above image shows one of the valid configurations of camera placement.

2. 算法思路

Greedy：

这道题完全没思路，直接看了solution，DP解法没看懂，直接看的Greedy，逻辑思路如下。

对于任何一个节点，它都有两种状态，有camera和没camera，其中没camera又分为两种，一种是它已经被covered了，另一种是还没有。所以一共是有三种状态。我们假设某节点和其左右孩子都需要被cover，那么我们首选肯定是在父节点放入camera，这样它才能辐射范围更广，而不是需要两个孩子放camera，camera更多。所以我们的核心策略就是尽可能把camera设置到上层，而不是叶子节点。

首先我们的定义一个节点的三种状态：

  1. 有camera – 2
  2. 无camera但是被cover了 – 1
  3. 无camera并且需要父亲节点carry – 0

对于null节点，我们不需要考虑，所以其状态为1。

所以逻辑如下：

  1. 如果当前节点的左右孩子有一个为2（有camera），则当前节点为1；
  2. 如果当前节点的左右孩子有一个为0（无camera，需要父亲带飞），则当前节点为2；
  3. 如果当前节点的左右孩子都为1（都不用父亲carry），则当前节点期待父节点carry，当前节点为0；
  4. 如果根节点为0（没被孩子带飞），则result+1。

时间复杂度为O(n)，空间复杂度O(h)。h为树的高度。

3. 解法

  1. Greedy
/**
 * 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) {
        return getCameraState(root) == 0 ? res + 1: res;
    }

    private int getCameraState(TreeNode node) {
        if (node == null) {
            return 1;
        }

        int leftState = getCameraState(node.left);
        int rightState = getCameraState(node.right);
        if (leftState == 1 && rightState == 1) {
            return 0; // 当前节点不放camera，期待被父亲carry
        } else if (leftState == 0 || rightState == 0) {
            res++;
            return 2; // 当前节点的孩子节点存在0状态，所以需要放一个camera
        } else { // 当前节点的孩子至少有一个2
            return 1;
        }
    }
}