DAY41：贪心算法（十）监控二叉树

968.监控二叉树

给定一个二叉树，我们在树的节点上安装摄像头。

节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。

计算监控树的所有节点所需的最小摄像头数量。

输入：[0,0,null,0,0]
输出：1
解释：如图所示，一台摄像头足以监控所有节点。

输入：[0,0,null,0,null,0,null,null,0]
输出：2
解释：需要至少两个摄像头来监视树的所有节点。 上图显示了摄像头放置的有效位置之一。

提示：

1. 给定树的节点数的范围是 [1, 1000]。
2. 每个节点的值都是 0。

思路

本题一个重要思路是，二叉树中一定是叶子节点数量大于根节点数量的。叶子节点和根节点比起来，数量呈现指数级的扩大，因此我们想要用最少的摄像头，就要在叶子节点上优先想如何节约摄像头。

在叶子节点的情况下，我们要优先在叶子节点的父节点上放摄像头，然后一层一层往上推，往上推的逻辑是每隔2个节点放一个摄像头。

遍历顺序

因为我们从叶子节点开始，从下往上处理二叉树，所以一定是后序遍历。遍历的同时，我们需要记录每个节点的状态，从而根据左右孩子的状态去确定父节点的状态。

这里就涉及到一个状态转移的问题，但是本题的状态转移和动规的状态转移不同，本题只是涉及到一个每个节点状态的判断，并不是要得到最优状态。本题中节点有三种状态：

• 0：无摄像头，无覆盖
• 1：有摄像头
• 2：无摄像头，有覆盖（在摄像头范围内）

我们在后序遍历的时候，可以通过状态转移，来判断左右孩子是某状态的时候，父节点应该是什么状态。

空节点处理

本题的目的，就是尽可能让叶子节点的父节点去放摄像头，这样摄像头数目才能最少。为了让叶子节点的父节点能放摄像头，空节点应该是有覆盖的状态。

也就是说，遇到空节点应该向上返回2，这样才能让叶子节点父节点有摄像头。

情况列举

• 当前节点左右孩子都无摄像头有覆盖，也就是状态2，此时当前节点必然是状态0

• 当前节点左右孩子至少有一个无覆盖，此时当前节点一定要装一个摄像头，也就是状态1，否则就不能全覆盖了

• 左右孩子至少有一个有摄像头，那么当前节点一定是2

• 最后一种情况是基于第一种情况，第一种情况的当前节点无覆盖，需要等待父节点去把他覆盖。但是第一种情况的节点，如果是根节点，就没有父节点可以装摄像头！

  此时根节点本身必须装一个摄像头，否则根节点就是无覆盖的状态。

本题所有可能的情况就限于这四种。主要是分析出来前三种，第四种是遍历到最后对根节点进行单独的判断。

最开始的写法

class Solution {
   
public:
    //摄像头个数
    int result=0;
    //后序遍历，有返回值，返回当前节点状态
    int travelsal(TreeNode* root){
   
        //后序终止条件
        if(root==nullptr) return 2;<
1
2
3
4
5
6
7
8
9