968-监控二叉树

LeetCode 968. 监控二叉树

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

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

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

示例 1：

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

示例 2：

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

method

• 0：表示无覆盖
• 1：表示有监控
• 2：表示有覆盖

空节点定义为有覆盖，采用后序遍历的方式

• 如果子节点都有覆盖了，则当前节点为无覆盖
• 只要子节点有一个无覆盖，当前节点就需要监控
• 只要子节点有一个有监控，当前节点就是有覆盖

int res;
int dfs(TreeNode *root) {
    if (!root) return 2;    // 空节点定义为已覆盖
    int left = dfs(root->left);
    int right = dfs(root->right);
    if (left == 2 && right == 2) return 0;  // 子节点都已覆盖，当前节点为无覆盖
    if (left == 0 || right == 0) {  // 子节点只要不覆盖，就必须监控
        res++;
        return 1;
    }
    if (left == 1 || right == 1) return 2;  // 子节点有监控，就已覆盖
    return -1;
}
int minCameraCover(TreeNode* root) {
    if (dfs(root) == 0) res++;
    return res;
}