968. Binary Tree Cameras #

Problem #

Given a binary tree, we install cameras on the nodes of the tree.

Each camera at a node can monitor its parent, itself, and its immediate children.

Calculate the minimum number of cameras needed to monitor all nodes of the tree.

Example 1:

Input: [0,0,null,0,0]
Output: 1
Explanation: One camera is enough to monitor all nodes if placed as shown.

Example 2:

Input: [0,0,null,0,null,0,null,null,0]
Output: 2
Explanation: At least two cameras are needed to monitor all nodes of the tree. The above image shows one of the valid configurations of camera placement.

Note:

1. The number of nodes in the given tree will be in the range [1, 1000].
2. Every node has value 0.

Problem Summary #

Given a binary tree, we install cameras on the nodes of the tree. Each camera on a node can monitor its parent, itself, and its immediate children. Calculate the minimum number of cameras needed to monitor all nodes of the tree.

Note:

1. The number of nodes in the given tree will be in the range [1, 1000].
2. Every node has value 0.

Solution Approach #

• Given a tree, the task is to place cameras on the tree. One camera can monitor at most 4 nodes: its 2 children, the node itself, and its parent. Ask for the minimum number of cameras needed to cover all nodes in the tree.
• This problem can be solved with a greedy idea. First divide nodes into 3 categories: the first category, leaf nodes; the second category, nodes that contain leaf nodes; the third category, nodes where one of the leaf nodes has a camera placed on it. Following this idea, color each node of the tree as shown below.

• For all nodes that contain leaf nodes, placing one camera there can cover at least 3 nodes, and if there is also a parent node, it can cover 4 nodes. So the greedy strategy is to start from the bottommost leaf nodes and “color” upward, first coloring the bottom layer as 1. Nodes marked 1 are all nodes where a camera should be placed. If a leaf node contains a node marked 1, then color this node as 2. As shown by the yellow nodes below. Yellow nodes represent nodes that do not need a camera, because they are covered by the camera on a leaf node. After nodes marked 2 appear, the nodes further upward again become leaf nodes 0. Continue in this way until reaching the root node.

• Finally, the root node still requires attention for multiple cases. The root node may be a leaf node 0, in which case the final answer still needs + 1, because a camera needs to be placed on the root node; otherwise the root node cannot be covered. The root node may also be 1 or 2; in these two cases, no additional camera is needed, because they are both covered. Following the method above, recursion can obtain the answer.

Code #

package leetcode

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

const (
	isLeaf status = iota
	parentofLeaf
	isMonitoredWithoutCamera
)

func minCameraCover(root *TreeNode) int {
	res := 0
	if minCameraCoverDFS(root, &res) == isLeaf {
		res++
	}
	return res
}

func minCameraCoverDFS(root *TreeNode, res *int) status {
	if root == nil {
		return 2
	}
	left, right := minCameraCoverDFS(root.Left, res), minCameraCoverDFS(root.Right, res)
	if left == isLeaf || right == isLeaf {
		*res++
		return parentofLeaf
	} else if left == parentofLeaf || right == parentofLeaf {
		return isMonitoredWithoutCamera
	} else {
		return isLeaf
	}
}