Leetcode968 Binary Tree Cameras

Posted on In

题目描述

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.

Eample 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.

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.

解析

这道题大概是说每个节点放一个相机，可以monitor父节点，自己以及直接的后继节点，要求求出最小放置的相机数量，使得整个二叉树都能被monitor到。

我们可以列举出每个被monitor节点有四种可能性，左子节点有相机，右子节点有相机，自己有相机或者父节点有相机。然后buttom up， 对于Leaf节点，如果在leaf放一个相机，自己和父节点可以cover，如果父节点放一个相机，父节点，两个子节点和父节点的父节点（parent’s parent）都能cover，也就是说对于所有leaf节点而言，在其父节点放一个相机，永远优于在leaf节点放相机。

有了这样一个推理，则可以利用Greedy的思路解决这个问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int res = 0;
public int minCameraCover(TreeNode root) {
    return preOrder(root) == 0 ? 1 + res : res; 
}

private int preOrder(TreeNode root){
    if(root == null)
        return 2;
    
    int left = preOrder(root.left);
    int right = preOrder(root.right);
    //两个子节点有一个没有被cover，则在该节点放一个相机
    if(left == 0 || right == 0){
        ++res;
        return 1;
    }
    //如果两个节点都被cover了且有一个上面有相机，则该节点被cover并且无需放相机
    // 如果两个节点都被cover但都没有相机，则该节点没有被cover，需要其父节点放一个相机
    return (left == 1 || right == 1) ? 2 : 0;
}

每个节点用0，1，2表示三种不同的状态:

  • 0表示这个节点没有被cover
  • 1表示这个节点上有一个相机
  • 2表示这个节点被cover了但没有相机

总结

一道很不错的Greedy算法题，评论区有一个很好的类比可以帮助我们理解这个算法背后的含义:

1
2
3
4
5
6
7
2---孤儿，不需要父母照顾
1---爸爸，可以照顾儿子和父母
0---啃老族：爸爸带带我。

两个后继都是孤儿时（2），不需要干任何事，可以化身啃老族（0）。
当你的后继里面有啃老族（0），你就必须成为爸爸（1）-----camera+1
当你的后继里面有爸爸（1）时，你又变成里不需要任何照顾的孤儿（2）

核心还是在于发现在父节点放相机永远优于在leaf节点放相机