968. Binary Tree Cameras

目录

题目描述

贪心

---

题目描述

968. 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 {int cnt_ = 0;//给每一个结点定义3个状态enum Status{COVERED = 1,//已被监控覆盖到UN_COVERED = 2,//还没有被监控覆盖到PLACED_CAMERA = 3//该位置放置有相机};
public:int minCameraCover(TreeNode* root) {if(monitor(root) == UN_COVERED)cnt_++;return cnt_++;}//返回root的状态Status monitor(TreeNode* root){if(root == nullptr){//叶子结点的孩子不存在，它们的状态应该设置为已覆盖，设置为其他两种状态都不行return COVERED;}auto L = monitor(root->left);auto R = monitor(root->right);if(L==UN_COVERED || R == UN_COVERED){cnt_++;return PLACED_CAMERA;}//上下两个判断的顺序不能颠倒if(L== PLACED_CAMERA || R == PLACED_CAMERA){return COVERED;}return UN_COVERED;}
};

如果不判断整个树的根节点是否被覆盖，则无法通过下面这种情形。

 如果颠倒了两个判断的先后顺序，则无法通过下面这种情形：