leetcode 968 监控二叉树

迷南。 2022-09-15 15:58 57阅读 0赞

## 前言 ##

题目：[968. 监控二叉树][968.]

参考题解：[监控二叉树-代码随想录][-]

--------------------

## 提交代码 ##

这道题目为hard。没想出来。看完答案之后，自己写了一遍。

<table> 
 <thead> 
  <tr> 
   <th></th> 
   <th align="center">贪心(核心)思路</th> 
   <th align="center">实现方法</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>思路-方法：part_1</td> 
   <td align="center">从下向上，不给叶子节点安装摄像头；</td> 
   <td align="center">后序遍历-&gt;从下向上；</td> 
  </tr> 
  <tr> 
   <td>思路-方法：part_2</td> 
   <td align="center">从下向上过程中，给不在摄像头覆盖范围内的节点安装摄像头；</td> 
   <td align="center">节点拥有<strong>状态</strong>，状态之间可以转换，根据状态决定是否安装摄像头；</td> 
  </tr> 
 </tbody> 
</table>

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 {
    private:
        enum {NOT_COVERED,COVERED,MONITOR}; // 枚举三种类型：无覆盖，有覆盖，有摄像头
        int result;
    
    public:
        int traverse(TreeNode* root){ 
            // 贪心思路：从下向上，不给叶子节点安装摄像头；向上过程中，给不在摄像头的覆盖范围内的节点安装摄像头。
    
            // 为了不使叶子节点安装摄像头，也不影响叶子是否覆盖情况。我们设所有叶子节点为“有覆盖情况”
            if(root == nullptr)
                return COVERED;
            
    
            int left_statue = traverse(root->left);
            int right_statue = traverse(root->right);
    
            // 如果左右孩子，都为“有覆盖”。由于下向上遍历，所以本节点必是“无覆盖”
            // 那这个节点是否需要安装摄像头呢？
            // 如果这个节点是叶子节点，不需要。
            // 唯二的另一种情况，该节点为根节点，则需要。
            // 所以，这里我们仅返回状态，不安装摄像头。当整个递归结束的返回值，即为根节点的状态，如果此时它为“无覆盖”，我们再加一即可
            if(left_statue == COVERED && right_statue == COVERED)
                return NOT_COVERED;
    
            // 从下向上，如果左右孩子，存在一个都“无覆盖”，本节点需要安装一个摄像头
            if(left_statue == NOT_COVERED || right_statue == NOT_COVERED){
                result++;
                return MONITOR;
            }
    
            // 左右孩子，有一个安装了摄像头，本节点不用安装，状态返回为“有覆盖”
            if(left_statue == MONITOR || right_statue == MONITOR)
                return COVERED;
    
            // return -1; // 呆呆的letcode，这里没有return，不让提交。但代码不会走到这里
        }
    
        int minCameraCover(TreeNode* root) {
            if(traverse(root) == NOT_COVERED)
                result++;
            return result;
        }
    };

[968.]: https://leetcode-cn.com/problems/binary-tree-cameras/
[-]: https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0968.%E7%9B%91%E6%8E%A7%E4%BA%8C%E5%8F%89%E6%A0%91.md