LeetCode#968

LeetCode#968监控二叉树

题目链接

一道在树上的dp问题，因为是树所以我们比较能简单的想到使用递归回溯的方法。（不停的遍历子节点，所以是递归回溯）而回溯的时候需要几种情况的参数，来辅助自己选择最小值。

三种情况：

• a：统计了整个树需要的摄像头数量，并且当前节点上安装了摄像头
• b: 统计了整个树需要的最少摄像头数量，并且当前节点可以选择不安装摄像头（意思是如果它的两个子结点中有一个安装了摄像头，当前节点就不需要安装了，需要具体考虑并取最小值，这是我们需要的最终结果）
• c: 统计了不考虑当前节点需要的最少摄像头数量（即只考虑它的子树需要的摄像头数量）

我们假设当前节点的左右节点返回的结果分别为la、lb、lc、ra、rb、rc
那么我们就有如下结论：

a = lc+rc+1 //左节点上不安装摄像头+右节点不安装摄像头+一个当前节点安装的摄像头
b = min(a,min(la+rb,lb+ra)) //两种情况，比较当前节点安装摄像头和当前节点不安装摄像头（如果当前节点不安装摄像头，那么它的子节点中必须有一个要安装摄像头，所以一定会选择la或ra，再加上另一棵树需要摄像头的最少情况）
c = min(a,lb+rb)//因为不考虑当前节点是否被监控，所以我们只需要判断两个子树需要最少摄像头的和即可（之所以和a比较是因为存在当前节点为叶子（空）节点的情况，下面会继续讨论）

那么如果当前节点为叶子节点呢？继续向下找的话，它的子节点都是空节点，空节点不能处于被选中的状态，所以空节点不存在a状态（即当前节点被选中安装摄像头）。但是为了方便递归回溯，我们采用统一的格式，所以为了避免出现错误的给空节点设置成a的情况，我们可以将空节点的初值调成特别大，这样就解决了空节点不能被选中的情况。

解决了这几个关键的问题，整个问题也就迎刃而解了，附一个代码：

class Solution {
public:
    struct status
    {
        int a,b,c;
    };
    status dfs(TreeNode *node)
    {
        if(node == nullptr)
        {
            return {999999,0,0};
        }
        auto [la,lb,lc] = dfs(node->left);
        auto [ra,rb,rc] = dfs(node->right);
        int a = lc+rc+1;
        int b = min(a,min(ra+lb,rb+la));
        int c = min(a,lb+rb);
        //cout << a << b << c << endl;
        return {a,b,c};
    }
    int minCameraCover(TreeNode* root) {
        auto [a,b,c] = dfs(root);
        return b;
    }
};