监控二叉树问题地址：https://leetcode-cn.com/problems/binary-tree-cameras/给定一棵二叉树，我们在树的节点上安装摄像头。节点上的每个摄像头都可以监控其父节点、自身及其直接子节点。计算监控树的所有节点所需的最少摄像机数量。示例1：输入：[0,0,null,0,0]输出：1解释：如图所示，一个摄像头足以监控所有节点。示例2：输入：[0,0,null,0,null,0,null,null,0]输出：2解释：至少需要两个摄像头来监控树的所有节点。上图显示了相机放置的有效位置之一。提示：给定树的节点数范围是[1,1000]。每个节点的值为0。思考这个问题，首先，如何放置相机才能使其最小？从问题中的例子中，我们其实可以得到启发。我们发现题例中的camera并没有放在叶子节点上！这是一个很重要的线索，摄像头可以覆盖上层、中层和下层。如果相机放在叶子节点上，一层的覆盖就会浪费掉。因此，将相机放置在叶子节点的父节点位置，可以充分利用相机的覆盖范围。那么有同学可能会问，为什么不从头节点开始，为什么要看叶子节点呢？因为如果头节点没有摄像头，就会省一个摄像头，如果叶节点没有摄像头，就会省摄像头的数量是指数级的。所以我们要从下往上看，局部最优：让叶子节点的父节点安装一个摄像头，使用最少数量的摄像头，整体最优：使用所有摄像头数量最少的！局部最优导致全局最优，找不到反例，那就遵循贪心原则吧！这时候一般的思路是从下往上开始，先在叶子节点的父节点上放一个摄像头，然后每隔两个节点放一个摄像头，直到到达二叉树的头节点。这个时候这个题目还有两个难点：如何遍历二叉树，每两个节点放一个摄像头，确定遍历顺序如何在二叉树中从下往上推导？可以使用后序遍历，也就是在左右的顺序，这样就可以在回溯的过程中，从下往上推导。后序遍历代码如下：inttraversal(TreeNode*cur){//空节点，节点有覆盖if(终止条件)return;intleft=traversal(cur->left);//leftintright=traversal(cur->right);//右逻辑处理//中间return;}注意上面代码中，我们取了左孩子的返回值和右孩子的返回值，即left和right，如何来推断未来中间节点的状态。一个相机此时需要一个状态转移公式。不要将它与动态状态转换公式混合使用。这道题没有选择最佳状态转移的过程，就是一个简单的状态转移！让我们看看这个状态应该如何转移。首先我们看一下每个节点可能有几种状态：有以下三种：这个节点没有覆盖这个节点有摄像头这个节点有覆盖我们有三个数字来表示：0：这个节点没有覆盖1：本节点有摄像头2：本节点有摄像头覆盖大家应该查不到第四个节点的状态。有的同学可能会疑惑是不是还有第四种状态：这个节点没有摄像头。其实没有摄像头就是没有覆盖或者覆盖的状态，所以一共还是三种状态。因为在遍历树的过程中，会遇到空节点，那么问题来了，空节点是一种什么样的状态呢？空节点意味着没有覆盖？意思是有摄像头？或者有覆盖吗？回归本质，为了摄像头的数量最少。尽量让叶子节点的父节点安装摄像头，使摄像头数量最少。那么空节点不能处于无覆盖状态，这样叶子节点就必须有摄像头，空节点不能处于有摄像头状态，这样叶子节点的父节点就不需要有摄像头，但是摄像头可以放在叶子节点的爷爷节点上。所以只能覆盖空节点的状态，这样才能把相机放到叶子节点的父节点上，接下来就是递归关系了。那么递归终止条件应该是遇到空节点，此时应该返回2（覆盖），原因上面已经解释过了。代码如下：//空节点，这个节点有一个函数覆盖if(cur==NULL)return2;递归，终止条件已经确定，我们来看单层逻辑处理。主要有以下四种情况：情况一：左右节点都被覆盖。左孩子被覆盖，右孩子被覆盖。那么此时中间节点应该处于无覆盖状态。如图：968.监控二叉树2的代码如下：//左右节点覆盖if(left==2&&right==2)return0;情况2：至少左右节点之一没有覆盖。如果满足以下条件，中间节点（父节点）应该放摄像头：left==0&&right==0左右节点无覆盖left==1&&right==0左节点有摄像头，右节点无coverageleft==0&&right==1左节点有无覆盖，右节点cameraleft==0&&right==2左节点无覆盖，右节点有覆盖left==2&&right==0左边节点有覆盖，右边节点没有覆盖这个不难理解，毕竟有子节点没有覆盖，父节点应该放置相机。这时候摄像头的数量应该加1，返回1表示中间节点会放置摄像头。代码如下：if(left==0||right==0){result++;return1;}情况三：左右节点至少有一个有摄像头。父节点应该是2（覆盖状态）left==1&&right==2左节点有摄像头，右节点有覆盖left==2&&right==1左节点有覆盖，右节点有摄像头left==1&&right==1左右节点都有摄像头代码如下：if(left==1||right==1)return2;从这段代码可以看出，如果left==1,right==0怎么办？其实这种情况在case2中已经判断过了，如图：968.监控二叉树1这种情况是也是大多数学生容易混淆的情况。情况四：头节点没有被覆盖。以上过程全部完成后，递归结束后，头结点可能仍然没有覆盖，如图：968.监控二叉树3.所以递归结束后，必须对根结点进行判断。如果没有Coverage，result++，代码如下：intminCameraCover(TreeNode*root){result=0;if(traversal(root)==0){//root没有覆盖result++;}returnresult;}我们就完成了分析了上面四种情况，代码也差不多了，整体代码如下：（我下面的代码注释很详细，为了弄清楚情况，特地把每种情况都列出来。）C++代码//version1classSolution{private:intresult;inttraversal(TreeNode*cur){//空节点，节点有覆盖if(cur==NULL)return2;intleft=traversal(cur->left);//leftintright=traversal(cur->right);//right//case1//左右节点都被覆盖if(left==2&&right==2)return0;//case2//left==0&&right==0左右节点都没有coverage//left==1&&right==0左节点有摄像头，右节点无覆盖//left==0&&right==1左节点有无覆盖，右节点有摄像头//left==0&&right==2左节点无coverage,右节点被覆盖//left==2&&right==0左节点被覆盖,右节点无覆盖if(left==0||right==0){result++;return1;}//Case3//left==1&&right==2左节点有摄像头，右节点有acoverage//left==2&&right==1左节点有coverage，右节点有camera//left==1&&right==1左右节点有camera//其他情况，前面的代码已经coveredif(left==1||right==1)return2;//上面代码中我没有使用else，主要是展示各种分支条件，让代码帮助读者理解//thisreturn-1逻辑不会在这里。return-1;}public:intminCameraCover(TreeNode*root){result=0;//case4if(traversal(root)==0){//根无覆盖result++;}returnresult;}};在上面代码的基础上，再进行精简，代码如下：//version2classSolution{private:intresult;inttraversal(TreeNode*cur){if(cur==NULL)return2;intleft=traversal(cur->left);//leftintright=traversal(cur->right);//rightif(left==2&&right==2)return0;elseif(left==0||right==0){result++;return1;}elsereturn2;}public:intminCameraCover(TreeNode*root){result=0;if(traversal(root)==0){//没有root覆盖结果++;}returnresult;}};你可能会惊讶它能这么短，其实它是在版本1的基础上，使用else直接覆盖一些情况。关于这个问题的解决办法，网上可以找到很多大神级的代码，但是都说不清楚。如果直接看代码，指定的越多，越看头晕，所以建议大家按照版本1的代码一步一步来。版本2没用！总结这道题的难点，首先要想到贪心的思想，然后就是遍历和状态推导。其实二叉树上状态推导的难度已经上升了一个档次，需要对二叉树的运算非常熟练。本文转载自微信公众号《代码随想录》，可通过以下二维码关注。转载本文请联系CodeCaprice公众号。
