README.md

968. 监控二叉树

English Version

题目描述

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

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

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

 

示例 1：

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

示例 2：

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

提示：

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

解法

Python3

Java

Go

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

var res int
func minCameraCover(root *TreeNode) int {
    res = 0
    //三种状态，后序遍历
    if root == nil {
        return 0
    }
    if dfs(root) == 0 {
        res++
    }
    return res
}
//0:待覆盖，1：已覆盖，2：安装

func dfs(root *TreeNode) int {
    if root == nil {
        return 1
    }
    l := dfs(root.Left)
    r := dfs(root.Right)
    //左右子节点存在待覆盖状态，当前节点要安装
    if l == 0 || r == 0 {
        res++
        return 2
    } else if l == 1 && r == 1 { //左右节点均为已覆盖，则当前节点为待覆盖
        return 0
    }
    //除上述情况外，左右子节点中至少有一个安装了监控，当前节点为已覆盖
    return 1
}