LeetCode 968.监控二叉树

https://leetcode-cn.com/problems/binary-tree-cameras/

难度：困难

给定一个二叉树，我们在树的节点上安装摄像头。

节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。

计算监控树的所有节点所需的最小摄像头数量。

示例 1：

输入：[0,0,null,0,0]

输出：1

解释：如图所示，一台摄像头足以监控所有节点。

示例 2：

输入：[0,0,null,0,null,0,null,null,0]

输出：2

解释：需要至少两个摄像头来监视树的所有节点。上图显示了摄像头放置的有效位置之一。

提示：

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

解法1：递归+状态判断

仔细思考，根据题目，我们可以知道，对于一个节点 node，它只可能会存在三种状态（下图中红色代表安装监控器，蓝色代表被监控到，绿色代表未被监控到，或是监控与未监控两者都可）：

node 任意一个孩子结点已安装监视器，那么当前 node 节点也会被监控到，这种状态记为 1；

关于下面右孩子的蓝色，这边解释一下，因为我们是从下往上遍历的，且因为一些条件判断，我们会保证遇到这种情况时，孩子结点会处于监控状态，具体可看代码。
node 任意一个孩子节点未安装监视器，且该孩子节点也未被监控到，那么当前节点必须安装监视器，这种状态我们记为 2；

node 的孩子节点都没安装监视器，但是都被监控到了，那么当前节点可以安装监视器，也可以不安装监视器，但是本着节省资源的目的，需要将这种情况返回给父节点，让父节点做裁断（到底是父节点安装，还是当前节点安装）。

JS 代码：

var minCameraCover = function(root) {
  let res = 0;
  
  const dfs = (node) => {
      if (!node) { // 对于空节点，默认其是未安装监视器且被监控到的状态
          return 3;
      }
  <span class="hljs-keyword">let</span> left = dfs(node.left), right = dfs(node.right);
  <span class="hljs-comment">// 若有一个孩子结点未被监控到，那么当前节点需要安装监控器，造成的结果就是返回父节点时，表现是安装了监控器</span>
  <span class="hljs-keyword">if</span> (left === <span class="hljs-number">2</span> || right === <span class="hljs-number">2</span>) &#123;
      res++;
      <span class="hljs-keyword">return</span> <span class="hljs-number">1</span>;
  &#125;
  <span class="hljs-comment">// 否则，若有一个孩子结点安装了监控器，当前节点会处于被监控的状态，且上面的判断语句已经排除了有孩子结点未被监控到的情况，因此当前节点返回到其父节点的表现就是没装监控器但是被监控到的情况</span>
  <span class="hljs-keyword">if</span> (left === <span class="hljs-number">1</span> || right === <span class="hljs-number">1</span>) &#123;
      <span class="hljs-keyword">return</span> <span class="hljs-number">3</span>;
  &#125;
  <span class="hljs-comment">// 否则，当前节点会处于未装监控器且未被监控到的情况，也就是状态 2.</span>
  <span class="hljs-keyword">return</span> <span class="hljs-number">2</span>;

};
if (dfs(root) === 2) {

res++;

}
return res;

};

:hexoPostRenderEscape–>

解法2：递归

解法2是官方的解题思路，看了几遍才看懂…因此附上一些自己的理解。

约定：若某棵树的所有节点都被监控，则称这棵树被覆盖。

设当前节点为 root，其左右孩子为 left 和 right 。若想要覆盖以 root 为根的树，那么有两种情况：

情况1：若给 root 设置了摄像头，那么其孩子节点 left、right 也会被监控到。此时只需要保证 left 和 right 的两棵子树也被覆盖即可。
情况2：若 root 没有设置摄像头，那么除了要保证以left为根结点的树和以right为根结点的树被覆盖之外，还需要保证 left 和 right 之中至少有一个节点安装了摄像头，这样 root 才能被监控到。

根据这两种情况，我们可以分析出，对于每个 root ，需要维护三种类型的状态：

状态 a ：root 必须安装摄像头的情况下（即情况1），覆盖整棵树需要的摄像头数量；
状态 b ：不论 root 是否安装摄像头，覆盖整棵树需要的摄像头数量；（也就是若 root 安置摄像头的话最好，不然 left 或 right 两个节点中需要至少一个有安置摄像头来保证 root 被监控）
状态 c ：不论 root 是否被监控到，覆盖两棵子树需要的摄像头数量；（对应着情况 1 和情况 2 中， left树和 right树被覆盖，而root 是否被监控表示 left 或 right 节点可能有安置摄像头，也可能未安置摄像头）

根据以上定义，一定有 a >= b >= c

设 root 节点的左右孩子节点left、right维护的状态变量为： $(l_a,l_b,l_c)$ 和 $(r_a,r_b,r_c)$ ，那么：

$a = l_c + r_c + 1$ ：即左右子树被覆盖所需的摄像头数量加上 root 安置的 1 个摄像头
$b = min(a, min(l_a + r_b, l_b + r_a))$ ：即两种情况中的最小值，情况 2 中需要 left 和 right 中至少一个节点设置摄像头来保证 root 被监控，因此是 left 设置 + right 未设置 与 left 未设置 + right 设置 这两种取值中的最小值。

对于状态 c 而言，只需要保证 left 和 right 两棵子树被覆盖即可（包括 left 和 right）。

那么，要么 root 处设置一个摄像头（保证 left 和 right 这两个节点被监控）的情况下left 和 right 的两棵子树刚好也被覆盖，那么就是状态a 的摄像头数量；

要么 root 处不放置摄像头，left 和 right 两棵子树保证自己被覆盖，所需的摄像头数量就是 $l_b + r_b$ 。

需要额外注意的是，对于 root 而言，如果其某个孩子为空，则不能通过在该孩子处放置摄像头的方式，监控到当前节点。因此，该孩子对应的变量 a 应当返回一个大整数，用于标识不可能的情形。

最终，根节点的状态变量 b 即为要求出的答案。

var minCameraCover = function(root) {
    const dfs = (root) => {
        if (!root) {
            return [Math.floor(Number.MAX_SAFE_INTEGER / 2), 0, 0];
        }
        const [la, lb, lc] = dfs(root.left);
        const [ra, rb, rc] = dfs(root.right);
        const a = lc + rc + 1;
        const b = Math.min(a, Math.min(la + rb, ra + lb));
        const c = Math.min(a, lb + rb);
        return [a, b, c];
    }

    return dfs(root)[1];
};

算法题解答 LeetCode

二叉树

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

Morris算法上一篇

ThreeJS快照下一篇