leetcode-968-Binary Tree Cameras

leetcode 968

问题

Given a binary tree, we install cameras on the nodes of the tree.

Each camera at a node can monitor its parent, itself, and its immediate children.

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

Example 1:

Input: [0,0,null,0,0]
Output: 1
Explanation: One camera is enough to monitor all nodes if placed as shown.

Example 2:

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.
**Note:**

1. The number of nodes in the given tree will be in the range [1, 1000].
2. Every node has value 0.

分析

对于树上的每一个叶子节点，在它上面放置摄像机的话，将会覆盖它自己以及它的父节点。

对于树上的根结点，如果在它上面放置摄像机的话，将会覆盖它自己以及它的两个孩子节点。

对于树上的其他节点，如果在它上面放置摄像机的话，将会覆盖它自己以及它的父节点和两个孩子节点。

那么对于在叶子节点放置摄像机而言，把摄像机放在它的父节点上，不仅会覆盖这个叶子节点，其父节点，还会覆盖它的兄弟节点和“爷爷”节点。

所以，对于在叶子节点放置摄像机而言，把摄像机放在它的父节点上总是最优的。

于是就产生了贪心策略：

1. 把所有摄像机放在所有叶子节点的父节点上，然后移除所有被覆盖的节点。
2. 重复步骤1直到所有的节点都被覆盖。

我们使用三种状态来表示子节点的情况。

0 表示叶子节点。

1 表示是叶子节点的父节点，这时需要一个照相机在它上面。

2 表示是一个被覆盖的节点，但没有照相机在它上面，也就是说是状态为 1 的节点的父节点。

对于我们的贪心策略。我们需要在放置了摄像机之后把所有的已经覆盖了的节点移除掉。因此，如果某个节点的两个孩子的状态都是 2 那么就认为它是“叶子”节点。

如果某个节点有一个子节点的状态是 0 那么就需要在它上面放置照相机，则它的状态就是 1。

如果某个节点有一个子节点状态是 1 （没有子节点是状态 0 的情况下）那么它就被覆盖，并且不需要放置照相机，状态为 2。

NOTE: 注意最后要对根节点做特殊的处理。

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int ans = 0;
    int minCameraCover(TreeNode* root) {
        int state = helper(root);
        return state == 0? ans+1: ans;
    }
    int helper(TreeNode *root) {
        if (!root) return 2;
        int l = helper(root->left);
        int r = helper(root->right);
        if (l == 0 || r == 0) {
            ans++;
            return 1;
        }
        return (l == 1 || r == 1)? 2: 0;
    }
};