问题：Leetcode 968. 监控二叉树
给定一个二叉树，我们在树的节点上安装摄像头。
节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
计算监控树的所有节点所需的最小摄像头数量。
/*** 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) {}* };*/
算法：
设定有三种状态：
- choose ：自己本身装摄像头，肯定能监控到父节点和孩子节点，所以孩子节点装不装都可以。这时候的最少摄像头为：min ( l_choose , l_by_fa ) + min ( r_choose , r_by_fa ) + 1
- by_fa ：自己的父节点装摄像头，自己可以被监控到，孩子节点顾好自己就行，所以孩子节点可以自己装，也可以不装被下面的节点监控到就行。这时候的最少摄像头为：min ( l_choose , l_by_children ) + min ( r_choose , r_by_children )
- by_children ：自己的孩子装摄像头，那么自己装不装都可以，那么其中一个孩子一定要装，所以情况是：（1）左孩子装，右孩子不装但能被监控到（ l_choose + r_by_children ) ；（2）右孩子装，左孩子不装但能被监控到（ r_choose + l_by_children ) ；（3）孩子都装：l_choose + r_choose 。这时候的最少摄像头为：min ( l_choose + r_by_children , r_choose + l_by_children , l_choose + r_choose )
时间复杂度：O ( n ) ，其中 n 为二叉树的节点个数。每个节点都会递归恰好一次。
空间复杂度：O ( n ) 。最坏情况下，二叉树是一条链，递归需要 O(n) 的栈空间。
代码：
class Solution {tuple<int,int,int> dfs(TreeNode *node){if(!node) return {INT_MAX/2,0,0};auto[l_choose,l_by_fa,l_by_children] = dfs(node->left);auto[r_choose,r_by_fa,r_by_children] = dfs(node->right);int choose = min(l_choose,l_by_fa) + min(r_choose,r_by_fa) + 1; // 自己本身装摄像头int by_fa = min(l_choose,l_by_children) + min(r_choose,r_by_children); // 自己的父节点装摄像头int by_children = min({l_choose + r_by_children,l_by_children + r_choose,l_choose + r_choose}); // 自己的孩子装摄像头return {choose,by_fa,by_children};}
public:int minCameraCover(TreeNode* root) {auto [choose,_,by_children] = dfs(root);return min(choose,by_children);}
};代码：
class Solution {
public:int result = 0;int dfs(TreeNode* Node){// 0-没有覆盖 1-有摄像头 2-有覆盖if(Node == NULL) return 2;int left = dfs(Node->left);int right = dfs(Node->right);// left == 0 || right == 0 和 left == 1 || right == 1的顺序不能调换if(left == 0 || right == 0){result++;return 1; // 子节点无监控，则父节点需要监控}if(left == 2 && right == 2) return 0;if(left == 1 || right == 1) return 2; // 子节点需要监控，则在此节点布置监控，父节点无需监控return -1;}int minCameraCover(TreeNode* root) {if(dfs(root) == 0) result++; // 根节点需要监控return result;}
};
