968.监控二叉树

链接：968.监控二叉树
难度：Hard
标签：树、深度优先搜索、动态规划、二叉树
简介：给定一个二叉树，我们在树的节点上安装摄像头。节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。计算监控树的所有节点所需的最小摄像头数量。

题解 1 - typescript

• 编辑时间：2020-09-22
• 执行用时：96ms
• 内存消耗：43MB
• 编程语言：typescript
• 解法介绍：[参考连接](https://leetcode-cn.com/problems/binary-tree-cameras/solution/jian-kong-er-cha-shu-by-leetcode-solution/)。

function minCameraCover(root: TreeNode | null): number {
  return dfs(root)[1];
  /**
   * @return
   * 状态 a：root 必须放置摄像头的情况下，覆盖整棵树需要的摄像头数目。
   * 状态 b：覆盖整棵树需要的摄像头数目，无论 root 是否放置摄像头。
   * 状态 c：覆盖两棵子树需要的摄像头数目，无论节点 root 本身是否被监控到。
   */
  function dfs(root: TreeNode | null): [number, number, number] {
    if (root === null) return [Infinity, 0, 0];
    const [la, lb, lc] = dfs(root.left);
    const [ra, rb, rc] = dfs(root.right);
    const a = lc + rc + 1;
    return [a, Math.min(a, la + rb, ra + lb), Math.min(a, lb + rb)];
  }
}

题解 2 - typescript

• 编辑时间：2021-04-04
• 执行用时：140ms
• 内存消耗：48.4MB
• 编程语言：typescript
• 解法介绍：递归计算每个点的存在摄像头和父节点存在摄像头的情况。

/**
 *    dp[0][0] 父节点和当前节点都不存在摄像头
 *    dp[1][0] 父节点存在摄像头，当前节点不存在
 *    dp[0][1] 父节点不存在摄像头，当前节点存在
 *    dp[1][1] 父节点和当前节点都存在摄像头
 */
function minCameraCover(root: TreeNode | null): number {
  const getArr = (): number[][] => new Array(2).fill(0).map(_ => new Array(2).fill(0));
  const dp: number[][] = getArr();
  const dfs = (node: TreeNode | null, dp: number[][]): void => {
    if (!node) {
      // 如果节点是null
      dp[1][0] = dp[0][0] = 0;
      dp[0][1] = dp[1][1] = Infinity; // null节点不存在摄像头
    } else if (!node.left && !node.right) {
      // 如果节点是叶子节点
      dp[0][0] = Infinity; // 不存在此种情况，叶子节点和父节点必须有一个有摄像头
      dp[1][1] = dp[0][1] = 1;
      dp[1][0] = 0;
    } else {
      const left: number[][] = getArr();
      const right: number[][] = getArr();
      dfs(node.left, left);
      dfs(node.right, right);
      dp[0][0] = Math.min(
        left[0][1] + right[0][0],
        left[0][0] + right[0][1],
        left[0][1] + right[0][1]
      ); // 如果父节点和当前节点都不存在摄像头，则子节点最少存在一个摄像头
      dp[1][0] = Math.min(left[0][0] + right[0][0], dp[0][0]); // 如果父节点存在摄像头，当前节点不存在，则子节点可以存在任意情况
      dp[1][1] = dp[0][1] =
        1 +
        Math.min(
          left[1][0] + right[1][0],
          left[1][1] + right[1][0],
          left[1][0] + right[1][1],
          left[1][1] + right[1][1]
        ); // 如果父节点不存在摄像头，当前节点存在，则子节点可存在任意情况，由于当前节点存在，则需增1
    }
  };
  dfs(root, dp);
  return Math.min(dp[0][1], dp[0][0]);
}