leetcode：968. 监控二叉树

题目

给定一个二叉树，我们在树的节点上安装摄像头。
节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
计算监控树的所有节点所需的最小摄像头数量。

提示：

  • 给定树的节点数的范围是 [1, 1000]。
  • 每个节点的值都是 0。

示例 1：
[困难] 968. 监控二叉树 - 图1

  1. 输入：[0,0,null,0,0]
  2. 输出：1
  3. 解释：如图所示，一台摄像头足以监控所有节点。

示例 2：
[困难] 968. 监控二叉树 - 图2

输入：[0,0,null,0,null,0,null,null,0]
输出：2
解释：需要至少两个摄像头来监视树的所有节点。 上图显示了摄像头放置的有效位置之一。

解答 & 代码

本题和[中等] 337. 打家劫舍 III类似，但是要多考虑一种不合法的情况 dp[node][2]

树形 DP（后序遍历）：
一、树形 DP 的定义：设当前节点为 node

  1. **dp[node][0]**：当前节点安装相机，以 node 为根节点的二叉树最少需要安装的相机数
  2. **dp[node][1]**：当前节点不安装相机，但当前节点能被子节点的监控覆盖（即至少有一个子节点安装了相机），以 node 为根节点的二叉树最少需要安装的相机数
  3. **dp[node][2]**：当前节点不安装相机，而且当前节点也不能被子节点的监控覆盖（即子节点也都没装相机），以 node 为根节点的二叉树最少需要安装的相机数

其中 dp[node][0] 和 dp[node][1] 是合法的；而当 node 为根节点时， dp[node][2] 是不合法的。
因此，最终题目的答案就是 **min(dp[root][0], dp[root][1])**。

二、状态转移方程：设 node 的左子节点为 left，右子节点为 right

  1. **dp[node][0]**：当前节点安装相机，以 node 为根节点的二叉树最少需要安装的相机数
  • 为当前节点安装了相机，因此子节点装不装相机都无所谓，因此从子节点的三个值中取最小值即可，都是合法的，即使是 dp[left][2] 也可取，因为 left 节点会被当前节点的监控覆盖
    dp[node][0] = 1 +                                            // 当前节点安装的相机
            min(dp[left][0], dp[left][1], dp[left][2]) +     // 左子树取最小值
            min(dp[right][0], dp[right][1], dp[right][2])    // 右子树取最小值
  1. **dp[node][1]**：当前节点不安装相机，但当前节点能被子节点的监控覆盖（即至少有一个子节点安装了相机），以 node 为根节点的二叉树最少需要安装的相机数
  • 当前节点不安装相机，但当前节点被子节点的监控，说明至少有一个子节点装了相机
    • case 1：左子节点装了相机，因此左子树只能取 dp[left][0]；右子节点有两种选择，要么也装了相机 dp[right][0]，要么没装相机但是被子节点的监控覆盖 dp[right][1]（但是不能取 dp[right][2] 因为 right 节点既没被子节点的监控覆盖、也没被父节点 node 的监控覆盖、自身也没装相机，所以不合法），因此从 dp[right][0] 和 dp[right][1] 取最小值即可
    • case 2：右子节点装了相机，分析同上
      dp[node][1] = min(
       dp[left][0] + min(dp[right][0], dp[right][1]),    // 左子节点装了相机
       dp[right][0] + min(dp[left][0], dp[left][1])    // 右子节点装了相机
      );
  1. **dp[node][2]**：当前节点不安装相机，而且当前节点也不能被子节点的监控覆盖（即子节点也都没装相机），以 node 为根节点的二叉树最少需要安装的相机数
  • 当前节点不安装相机，且当前节点也不能被子节点的监控覆盖，说明子节点都没装相机，但是为了保证子节点合法，子节点只能选择 dp[left][1] 和 dp[right][1]
  • 不能选择 dp[left][2] 和 dp[right][2]，因为这样子节点自身没装监控，也不能被其子节点的监控覆盖，也不能被父节点监控（因为 node 节点也没装相机），这样子节点 left 和 right 就是不合法的
    dp[node][2] = dp[left][1] + dp[right][1];

三、初始化：

  • 对于空节点（node == nullptr）：空节点的初始化值不能对空节点的父节点是否要安装相机的考虑产生影响
    • **dp[nullptr][0] = MAX_VAL**：
      • 空节点肯定装不了相机，因此这个值不能取。因此将其设为 MAX_VALUE（本题最多 1000 个节点，因此 MAX_VAL 可以设为 1001），使得后续取 min 的操作不会取到这个值
      • 令，如果选了这个值，说明空节点装了相机，然后其父节点就可以不装相机，因为父节点未被空节点的相机监控到，而实际上并不会有这个相机！
    • **dp[nullptr][1] = 0**：不会对父节点产生影响
    • **dp[nullptr][2] = MAX_VAL**：空节点不能装相机这点是满足的；但是如果空节点不能被子节点的监控覆盖，那么在取这个值的时候，其父节点必须装相机，否则空节点会不合法，因此这影响了父节点的选择 ```cpp /**
      • 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) {}
      • }; */ const int MAX_VAL = 1001;

class Solution { private: // 树形 DP（后序遍历） vector postOrder(TreeNode* root) { vector dp(3); // 递归结束条件：空节点，初始化后直接返回 if(root == nullptr) { dp[0] = MAX_VAL; // 不能取 dp[1] = 0; // 可以取，不影响父节点的判断 dp[2] = MAX_VAL; // 不能取 return dp; }

    // 递归得到左、右子树的结果
    vector<int> dpLeft = postOrder(root->left);
    vector<int> dpRight = postOrder(root->right);

    // 状态转移
    // dp[0] 代表当前节点安装相机，因此左、右子节点是否安装都无所谓
    dp[0] = 1 +                                                // 当前节点安装的相机
            min(dpLeft[0], min(dpLeft[1], dpLeft[2])) +     // 左子树取最小值
            min(dpRight[0], min(dpRight[1], dpRight[2]));    // 右子树取最小值
    // dp[1] 代表当前节点不安装相机，但当前节点能被子节点的监控覆盖，因此只有有一个子节点装了相机
    dp[1] = min(
        dpLeft[0] + min(dpRight[0], dpRight[1]),            // 左子节点装了相机
        dpRight[0] + min(dpLeft[0], dpLeft[1]));            // 右子节点装了相机
    // dp[2] 代表当前节点不安装相机，且当前节点不能被子节点的监控覆盖，因此子节点都没装监控
    // 又，子节点要想合法，只能被其子节点的监控覆盖，因此只能取 dpLeft[1] 和 dpRight[1]
    dp[2] = dpLeft[1] + dpRight[1];
    return dp;
}

public: int minCameraCover(TreeNode* root) { vector result = postOrder(root); return min(result[0], result[1]); } };

复杂度分析：设二叉树节点数为 N

- 时间复杂度 O(N)：
- 空间复杂度 O(logN)：递归栈深度 = 树深度

执行结果：

执行结果：通过

执行用时：24 ms, 在所有 C++ 提交中击败了 12.89% 的用户 内存消耗：26.5 MB, 在所有 C++ 提交中击败了 5.00% 的用户 ```