Task

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.

Examples

Example 1: leetcode968_1

1
2
3

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

Example 2: leetcode968_2

1
2
3

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:

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

Solution

  • 为每个节点设置3种state：
    • NONE表示该节点未被覆盖到
    • COVERED表示该节点已经被其他节点上的相机覆盖到
    • CAMERA表示该节点上有相机
  • DFS后序遍历树，从叶子节点向上递归：
    • 叶子节点之下的空节点（递归终点）默认已被覆盖到
    • 若该节点的某个子节点未被覆盖，则在该节点上放置相机（因为不再访问子节点，只有在这里放相机才能覆盖到它）
    • 若该节点的某个子节点上有相机，则该节点标记为COVERED（注意：必须考虑完上一种情形才能考虑这一种情形，因为若一个节点的左子节点未被覆盖而右子节点上有相机，若顺序互换后该节点是COVERED而不是CAMERA，左子节点永远不会被覆盖到）
    • 若该节点既没有相机子节点，又没有未被覆盖的子节点，则该节点将会被其父节点覆盖，只需将该节点标记为NONE
  • 时间复杂度：每个节点只看一次，O(n)
  • 空间复杂度：取决于树的高度，O(h)
 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
42
43
44

// Runtime: 8 ms, faster than 98.49% of C++ online submissions for Binary Tree Cameras.
// Memory Usage: 21.2 MB, less than 77.71% of C++ online submissions for Binary Tree Cameras.
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int minCameraCover(TreeNode* root) {
        //若最后根节点未被覆盖，则在根节点上放相机
        if(dfs(root)==NONE) ++num;
        return num;
    }
private:
    //每个节点的状态
    enum state{NONE=0,COVERED=1,CAMERA=2};
    state dfs(TreeNode *root){
        //空节点默认被cover到，终止递归
        if(!root) return COVERED;
        //后序遍历，由左右子节点的状态得到当前节点应该具有的状态
        state l=dfs(root->left);
        state r=dfs(root->right);
        //只要有一个子节点为空，就在当前节点上放相机
        if(l==NONE || r==NONE){
            ++num;
            return CAMERA;
        }
        //只要有一个子节点上有相机，当前节点就被cover
        //两个if不能互换，因为要处理“一个子节点为NONE另一个子节点为CAMERA”的情形
        if(l==CAMERA || r==CAMERA)
            return COVERED;
        //若子节点都是被cover但无相机的情形，则该节点标记为NONE，将在其父节点上放相机
        return NONE;
    }
    //维护计数，是最终返回的结果
    int num=0;
};