【力扣】968. 监控二叉树

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

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

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

示例 1：

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

示例 2：

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

提示：

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

题解：

贪心算法（递归 后序遍历+回溯）：

func minCameraCover(root *TreeNode) int {
	result := 0
	var dfs func(node *TreeNode) int
	/*
		节点的状态值：
		0. 表示无覆盖
		1. 表示有摄像头
		2. 表示有覆盖
		后序遍历，根据左右节点状态来判断自己的状态
	*/
	dfs = func(node *TreeNode) int {
		if node == nil {
			// 空节点默认为有覆盖状态，避免在叶子节点上装摄像头
			return 2
		}
		left := dfs(node.Left)
		right := dfs(node.Right)
		// 如果左右节点都覆盖了的话，那么本节点的状态应该就是无覆盖，没有摄像头
		if left == 2 && right == 2 {
			return 0
		}
		// 如果左右节点都是无覆盖的状态，那么本节点应该放一个摄像头
		if left == 0 || right == 0 {
			result++
			return 1
		}
		// 如果左右节点至少有 1 个摄像头，那么本节点就属于被覆盖的状态
		if left == 1 || right == 1 {
			return 2
		}
		return -1
	}
	// 对跟节点做校验，防止出现根节点是无覆盖的状态
	if dfs(root) == 0 {
		result++
	}
	return result
}