LeetCode-968. 监控二叉树

问题地址

LeetCode每日一题/2020-09-22

LeetCode968. 监控二叉树

问题描述

规则

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

示例

• 示例一：
  

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

• 示例二：
  

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

提示

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

解析

解题思路

• 根据题意，我们给节点定义一些状态：
  • 0：空白节点；
  • 1：被监控节点；
  • 2：监控节点；
• 我们通过自下向上采用后序遍历的方式遍历二叉树，即根据子节点状态推断根节点的状态；

数据操作分析

• 遍历左节点->得到左节点及更新后的状态;
• 遍历右节点->得到右节点及更新后的状态；
• 根据左右节点推断根节点状态；

复杂度分析

1. 时间复杂度
2. 空间复杂度

编码实现

/**
 * LeetCode0958
 */
public class LeetCode0958_BinaryTreeCameras {
    int sum;

    public int minCameraCover(TreeNode root) {
        if (dfs(root).val == 0) sum++;
        return sum;
    }

    private TreeNode dfs(TreeNode root) {
        if (root == null) {
            root = new TreeNode(1);
            return root;
        }
        TreeNode left = dfs(root.left);
        TreeNode right = dfs(root.right);

        if (left.val == 1 && right.val == 1) {
            root.val = 0;
        } else if (left.val == 0 || right.val == 0) {
            sum++;
            root.val = 2;
        } else if (left.val == 2 || right.val == 2) {
            root.val = 1;
        }
        return root;
    }
}

官方解法

方法一：递归

思路：

• 本题中要求我们将每个节点的值修改为原来的节点值加上所有大于它的节点值之和。这样我们只需要反序中序遍历该二叉搜索树，记录过程中的节点值之和，并不断更新当前遍历到的节点的节点值，即可得到题目要求的累加树。
• 本题以二叉树为背景，不难想到用递归的方式求解。本题的难度在于如何从左、右子树的状态，推导出父节点的状态。
• 为了表述方便，我们约定：如果某棵树的所有节点都被监控，则称该树被「覆盖」。
• 假设当前节点为 \textit{root}，其左右孩子为 \textit{left}, \textit{right}。如果要覆盖以 \textit{root} 为根的树，有两种情况：
  • 若在 \textit{root} 处安放摄像头，则孩子 \textit{left}, \textit{right} 一定也会被监控到。此时，只需要保证 \textit{left} 的两棵子树被覆盖，同时保证\textit{right} 的两棵子树也被覆盖即可。
  • 否则， 如果 \textit{root} 处不安放摄像头，则除了覆盖 \textit{root} 的两棵子树之外，孩子 \textit{left}, \textit{right} 之一必须要安装摄像头，从而保证 \textit{root} 会被监控到。
• 根据上面的讨论，能够分析出，对于每个节点 \textit{root} ，需要维护三种类型的状态：
  • 状态 a：\textit{root} 必须放置摄像头的情况下，覆盖整棵树需要的摄像头数目。
  • 状态 b：覆盖整棵树需要的摄像头数目，无论 \textit{root} 是否放置摄像头。
  • 状态 c：覆盖两棵子树需要的摄像头数目，无论节点 \textit{root} 本身是否被监控到。
• 根据它们的定义，一定有 a \geq b \geq c。
• 对于节点 \textit{root} 而言，设其左右孩子 \textit{left}, \textit{right} 对应的状态变量分别为 (l_a,l_b,l_c) 以及 (r_a,r_b,r_c)。根据一开始的讨论，我们已经得到了求解 a,b 的过程：
• 状态a = l_c + r_c + 1
• 状态b = \min(a, \min(l_a + r_b, r_a + l_b))b
• 对于 c 而言，要保证两棵子树被完全覆盖，要么 \textit{root} 处放置一个摄像头，需要的摄像头数目为 a；要么 \textit{root} 处不放置摄像头，此时两棵子树分别保证自己被覆盖，需要的摄像头数目为 l_b + r_b 。
• 需要额外注意的是，对于 \textit{root} 而言，如果其某个孩子为空，则不能通过在该孩子处放置摄像头的方式，监控到当前节点。因此，该孩子对应的变量 aa 应当返回一个大整数，用于标识不可能的情形。最终，根节点的状态变量 b 即为要求出的答案。

复杂度分析：

1. 时间复杂度:O(N)，其中 N 为树中节点的数量。对于每个节点，我们在常数时间内计算出 a,b,c 三个状态变量。

2. 空间复杂度：O(N)。每次递归调用时，我们需要开辟常数大小的空间存储状态变量的取值，而递归栈的深度等于树的深度，即 O(N)。

编码实现

class Solution {
    public int minCameraCover(TreeNode root) {
        int[] array = dfs(root);
        return array[1];
    }

    public int[] dfs(TreeNode root) {
        if (root == null) {
            return new int[]{Integer.MAX_VALUE / 2, 0, 0};
        }
        int[] leftArray = dfs(root.left);
        int[] rightArray = dfs(root.right);
        int[] array = new int[3];
        array[0] = leftArray[2] + rightArray[2] + 1;
        array[1] = Math.min(array[0], Math.min(leftArray[0] + rightArray[1], rightArray[0] + leftArray[1]));
        array[2] = Math.min(array[0], leftArray[1] + rightArray[1]);
        return array;
    }
}

精彩评论

跳转地址1：「手画图解」从递归优化到树形DP

思路：

• 这道题和 打家劫舍III 很像，同样是二叉树，打家劫舍规定不能打劫相邻的节点，求打劫节点值的最大收益。对于每个节点，要么打劫，要么不打劫，描述一个子树的最大收益需要两个变量：它的根节点，是否打劫根节点。
• 对于一个节点，它有什么状态，仅仅是放不放相机吗？还有是否被监控到。两者可以重叠吗？是可以的，被监控到的节点也可以放相机的。描述一个节点的状态有三个：节点本身（不同的子树相互区分，代表不同的子问题），是否放了相机，是否被监控到。
• 我们定义一个递归函数 minCam：计算出：以当前 root 为根节点的子树，需要放置的最少相机数。
• 把整个树的 minCam 问题分解为子树的 minCam 问题，位于底部的 base case 是易得的，自上而下地调用，答案会自下而上地返回。
• 递归函数 minCam 接收的参数：
  • 当前遍历的 root 节点。
  • placeCam：root 是否放置相机。
  • watched：root 是否被父亲或自己监控。
• 因为递归是自上而下地思考，所以 watched 不含被儿子监控的情况，只代表是否被父亲或自己监控。（是否被儿子监控要分类讨论，交给子调用解决）

分情况讨论

• 当前节点 root 放了相机（当前子树的相机数，保底为1）
  • 儿子都没有放相机，儿子被父亲监控
    minCam(root.left, false, true) + minCam(root.right, false, true)
  • 左儿子放了相机，被监控，右儿子没有相机，被父亲监控
    minCam(root.left, true, true) + minCam(root.right, false, true)
  • 左儿子没有相机，被父亲监控，右儿子放了相机，被监控
    minCam(root.left, false, true) + minCam(root.right, true, true)
• 当前节点 root 没有相机，但被父亲监控了
  • 两个儿子都放了相机，被监控
  • 左儿子放了相机，被监控，右儿子没有相机，没有被父亲和自己监控，但被自己儿子监控
  • 右儿子放了相机，被监控，左儿子没有相机，没有被父亲和自己监控，但被自己儿子监控
  • 两个儿子都没有相机，没有被父亲和自己监控，但被自己儿子监控
• 当前节点 root 没有相机，也没有被父亲监控，是被儿子监控
  • 两个儿子都放了相机，被监控
  • 左儿子有相机，被监控，右儿子没有相机，没被父亲和自己监控，被自己儿子监控
  • 左儿子没有相机，没被父亲和自己监控，被自己儿子监控。右儿子有相机，被监控

算法

递归入口

• 整个树的根节点被监控的有两种情况：
  • 根节点有相机
  • 根节点没有相机，并且根节点没有父亲，没有被父亲监控，但被儿子监控
• 主函数对根节点调用两次 minCam，返回较小的一个。

const minCameraCover = (root) => {
  const minCam = (root, placeCam, watched) => { 
    // 省略
  };
  return Math.min(
    minCam(root, true, true),  // 根节点有相机
    minCam(root, false, false) // 根节点没有相机，因为没有父亲，没有被父亲监控，是被儿子监控
  );
};

递归的结束条件

• 也就是我们的 base case。当遍历到 null 节点时

if (root == null) {  // 遍历到null节点
  if (placeCam) {    // 如果父节点要求自己有相机，但null节点不可能有
    return Infinity; // 返回一个无穷大，让这个选择失效，被忽略掉（因为Math.min）
  } else {           // 因为null没有相机，null没有子节点，下面也没有相机，返回0
    return 0;
  }
}

编码实现

 const minCameraCover = (root) => {
  // 以root为根节点的子树，放置的最少相机数，placeCam：root是否放了相机，watched：root是否被父亲或自己监控
  const minCam = (root, placeCam, watched) => {
    if (root == null) {  // 遍历到null节点
      if (placeCam) {    // 如果父节点要求自己有相机，但null节点不可能有
        return Infinity; // 返回一个无穷大，让这个选择失效
      } else {
        return 0;
      }
    }
    if (placeCam) {  // root放置相机
      return 1 + Math.min( // root放了相机，要加1
        minCam(root.left, false, true) + minCam(root.right, false, true), 
        minCam(root.left, true, true) + minCam(root.right, false, true), 
        minCam(root.left, false, true) + minCam(root.right, true, true) 
      );  
    } else {
      if (watched) { // root没放相机，但被父亲监控了
        return Math.min(
          minCam(root.left, true, true) + minCam(root.right, true, true),
          minCam(root.left, true, true) + minCam(root.right, false, false), 
          minCam(root.left, false, false) + minCam(root.right, true, true), 
          minCam(root.left, false, false) + minCam(root.right, false, false) 
        );
      } else {  // root没有相机，也没被父亲监控，被儿子监控了
        return Math.min(
          minCam(root.left, true, true) + minCam(root.right, true, true), 
          minCam(root.left, true, true) + minCam(root.right, false, false), 
          minCam(root.left, false, false) + minCam(root.right, true, true) 
        );
      }
    }
  };

  return Math.min(
    minCam(root, true, true),  // 根节点有相机
    minCam(root, false, false) // 根节点没有相机，因为没有父亲，没有被父亲监控，是被儿子监控
  );
};

执行结果

• 遇到如下案例时会超时
  

优化

• 怎么优化？哪里做了重复的计算？
  • 我们对左右子树的调用，传的参数就有大量重复，有很多次相同的调用。
  • 我们这样，对于每一个子树，即每一个子问题，即每一次递归调用，都计算三种状态，即上面所述的三种情况：
    • withCam ：当前子树的根节点有相机
    • noCamWatchByDad：当前节点 root 没有相机，被父亲监控
    • noCamWatchBySon ：当前节点 root 没有相机，被儿子监控
  • 对于一个子树的根节点，它的相机拥有情况，无非就这三种，把它们放入一个对象，return 出来，即三个状态的计算结果暴露给父调用，供它参考。
    return { withCam, noCamWatchByDad, noCamWatchBySon };
  • 那么，当前的递归调用，要参考子调用的结果，所以要调用左右子树，根据子树的情况，计算出当前树的三个状态：withCam、noCamWatchByDad、noCamWatchBySon。

const left = minCam(root.left);
const right = minCam(root.right);

• 这样，我们一次递归调用，就只执行两次子调用。随着递归的全部出栈，最后的大问题（整个树）的 minCam 数目被求出来。

优化后代码

const minCameraCover = (root) => {
  const minCam = (root) => {
    if (root == null) {   // base case
      return {
        withCam: Infinity,
        noCamWatchByDad: 0,
        noCamWatchBySon: 0
      };
    }
    const left = minCam(root.left);   // 以左儿子为根的左子树的情况
    const right = minCam(root.right); // 以右儿子为根的右子树的情况
    // 下面相当于状态转移方程
    const withCam = 1 + Math.min(     
      left.noCamWatchByDad + right.noCamWatchByDad,
      left.withCam + right.noCamWatchByDad,
      left.noCamWatchByDad + right.withCam
    );

    const noCamWatchByDad = Math.min(
      left.withCam + right.withCam,
      left.withCam + right.noCamWatchBySon,
      left.noCamWatchBySon + right.withCam,
      left.noCamWatchBySon + right.noCamWatchBySon
    );

    const noCamWatchBySon = Math.min(
      left.withCam + right.withCam,
      left.withCam + right.noCamWatchBySon,
      left.noCamWatchBySon + right.withCam
    );

    return { withCam, noCamWatchByDad, noCamWatchBySon };
  };

  const res = minCam(root); // 相当于 dp[root]
  return Math.min(res.withCam, res.noCamWatchBySon); // 相当于 dp[root][0] 和 dp[root][2]
};

复盘总结，随便聊聊

树形 DP 不像常规 DP 那样在迭代中 “填表”，而是在递归遍历中 “填表”。
这里没有开辟 DP 数组去存中间状态，而是通过子调用将状态返回出去，提供给父调用，其实就是动态规划填表的思想。
因为动态规划就是：根据过去的状态求出当前状态，按顺序一个个求出来。这里是沿着一棵树去求解子问题，可以理解为在一棵树上填表。
可以理解为：递归调用栈把中间计算结果暂存了，子调用的结果“交付”给父调用，它就销毁了，并没有加入记忆化，不是记忆化递归。
当然，你也可以开辟一个 DP 容器，key 是 root 节点（子树），因此无法用数组，那就用 HashMap，value 是子树的计算结果。
可以，但没必要，因为不需要存储中间计算结果。
随着递归的出栈，子调用不断向上返回，子问题（子树）被一个个解决。最后求出大问题：整个树的最小相机数。

跳转地址2：968. 监控二叉树:【递归上的状态转移】详解

思路

• 这道题目其实不是那么好理解的，题目举的示例不是很典型，会误以为摄像头必须要放在中间，其实放哪里都可以只要覆盖了就行。这道题目难在两点：
  • 需要确定遍历方式
  • 需要状态转移的方程
• 我们之前做动态规划的时候，只要最难的地方在于确定状态转移方程，至于遍历方式无非就是在数组或者二维数组上。
• 而本题，不仅要确定状态转移方式，而且要在树上进行推导，所以难度就上来了，一些同学知道这道题目难，但其实说不上难点究竟在哪。
• 需要确定遍历方式
  • 首先先确定遍历方式，才能确定转移方程，那么该如何遍历呢？
  • 在安排选择摄像头的位置的时候，我们要从底向上进行推导，因为尽量让叶子节点的父节点安装摄像头，这样摄像头的数量才是最少的
  • 如何从低向上推导呢？
  • 就是后序遍历也就是左右中的顺序，这样就可以从下到上进行推导了。
  • 后序遍历代码如下：

    int traversal(TreeNode* cur) {

        // 空节点，该节点有覆盖
        if (终止条件) return ;

        int left = traversal(cur->left);    // 左
        int right = traversal(cur->right);  // 右

        逻辑处理                            // 中

        return ;
    }

注意在以上代码中我们取了左孩子的返回值，右孩子的返回值，即left 和 right， 以后推导中间节点的状态

• 需要状态转移的方程
  • 确定了遍历顺序，再看看这个状态应该如何转移，先来看看每个节点可能有几种状态：
    • 该节点无覆盖
    • 本节点有摄像头
    • 本节点有覆盖
  • 我们分别有三个数字来表示：
    • 0：该节点无覆盖
    • 1：本节点有摄像头
    • 2：本节点有覆盖
  • 那么问题来了，空节点究竟是哪一种状态呢？ 空节点表示无覆盖？ 表示有摄像头？还是有覆盖呢？
    • 回归本质，为了让摄像头数量最少，我们要尽量让叶子节点的父节点安装摄像头，这样才能摄像头的数量最少。
    • 那么空节点不能是无覆盖的状态，这样叶子节点就可以放摄像头了，空节点也不能是有摄像头的状态，这样叶子节点的父节点就没有必要放摄像头了，而是可以把摄像头放在叶子节点的爷爷节点上。
    • 所以空节点的状态只能是有覆盖，这样就可以在叶子节点的父节点放摄像头了
  • 接下来就是递推关系。
    • 那么递归的终止条件应该是遇到了空节点，此时应该返回2（有覆盖），原因上面已经解释过了。代码如下：

        // 空节点，该节点有覆盖
        if (cur == NULL) return 2;

• 递归的函数，以及终止条件已经确定了，再来看单层逻辑处理。主要有如下三大类情况：
• 情况1:
  • 左孩子有覆盖，右孩子有覆盖，那么此时中间节点应该就是无覆盖的状态了。
    

        // 左右节点都有覆盖
        if (left == 2 && right == 2) return 0;

• 情况2:
  • 如果是以下情况，则中间节点（父节点）应该放摄像头：

left == 0 && right == 0 左右节点无覆盖
left == 1 && right == 0 左节点有摄像头，右节点无覆盖
left == 0 && right == 1 左节点有无覆盖，右节点摄像头
left == 0 && right == 2 左节点无覆盖，右节点覆盖
left == 2 && right == 0 左节点覆盖，右节点无覆盖
这个不难理解，毕竟有一个孩子没有覆盖，父节点就应该放摄像头。
此时摄像头的数量要加一，并且return 1，代表中间节点放摄像头。

- 代码如下：

        if (left == 0 || right == 0) {
            result++;
            return 1;
        }

• 情况3
  • 如果是以下情况，其实就是 左右孩子节点有一个有摄像头了，那么其父节点就应该是2（覆盖的状态）

left == 1 && right == 2 左节点有摄像头，右节点有覆盖
left == 2 && right == 1 左节点有覆盖，右节点有摄像头
left == 1 && right == 1 左右节点都有摄像头

- 代码如下：

        if (left == 1 || right == 1) return 2;

从这个代码中，可以看出，如果left 1, right 0 怎么办？其实这种条件在情况2中已经判断过了，如图：

• 情况4
  • 以上都处理完了，递归结束之后，可能头结点 还有一个无覆盖的情况，如图：
    
  • 所以递归结束之后，还要判断根节点，如果没有覆盖，result++，代码如下：

    int minCameraCover(TreeNode* root) {
        result = 0;
        if (traversal(root) == 0) { // root 无覆盖
            result++;
        }
        return result;
    }

编码实现

class Solution {
private:
    int result;
    int traversal(TreeNode* cur) {

        // 空节点，该节点有覆盖
        if (cur == NULL) return 2;

        int left = traversal(cur->left);    // 左
        int right = traversal(cur->right);  // 右

        // 情况1
        // 左右节点都有覆盖
        if (left == 2 && right == 2) return 0;

        // 情况2
        // left == 0 && right == 0 左右节点无覆盖
        // left == 1 && right == 0 左节点有摄像头，右节点无覆盖
        // left == 0 && right == 1 左节点有无覆盖，右节点摄像头
        // left == 0 && right == 2 左节点无覆盖，右节点覆盖
        // left == 2 && right == 0 左节点覆盖，右节点无覆盖
        if (left == 0 || right == 0) {
            result++;
            return 1;
        }

        // 情况3
        // left == 1 && right == 2 左节点有摄像头，右节点有覆盖
        // left == 2 && right == 1 左节点有覆盖，右节点有摄像头
        // left == 1 && right == 1 左右节点都有摄像头
        // 其他情况前段代码均已覆盖
        if (left == 1 || right == 1) return 2;

        // 以上代码我没有使用else，主要是为了把各个分支条件展现出来，这样代码有助于读者理解
        // 这个 return -1 逻辑不会走到这里。
        return -1;
    }

public:
    int minCameraCover(TreeNode* root) {
        result = 0;
        // 情况4
        if (traversal(root) == 0) { // root 无覆盖
            result++;
        }
        return result;
    }
};