Leetcode 968. 监控二叉树 树形dp、状态机 C++实现

问题：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) {}* };*/

算法：

设定有三种状态：

1. choose ：自己本身装摄像头，肯定能监控到父节点和孩子节点，所以孩子节点装不装都可以。这时候的最少摄像头为：min ( l_choose ,  l_by_fa ) + min ( r_choose ,  r_by_fa ) + 1
2. by_fa ：自己的父节点装摄像头，自己可以被监控到，孩子节点顾好自己就行，所以孩子节点可以自己装，也可以不装被下面的节点监控到就行。这时候的最少摄像头为：min ( l_choose ,  l_by_children ) + min ( r_choose ,  r_by_children )
3. 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;}
};