968.监控二叉树

监控二叉树

给定二叉树，在节点上安装摄像头。每个摄像头可以监视自身、父节点和子节点。返回监控所有节点所需的最小摄像头数。

示例 1:

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

提示:

• 树中节点数在 1 到 1000 之间
• 每个节点值在 0 到 10000 之间

解析

DFS 返回三种状态：已覆盖但无摄像头、需安装摄像头、无法覆盖需父节点监控。

var minCameraCover = function (root) {
  let result = 0;

  const dfs = (node) => {
    if (!node) return 0;

    const left = dfs(node.left);
    const right = dfs(node.right);

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

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

    return -1;
  };

  const status = dfs(root);
  return status === -1 ? result + 1 : result;
};

时间复杂度 O(N)，空间复杂度 O(H)。