Binary Tree Cameras
Problem Description
You are given the root of a binary tree. We install cameras on the tree nodes where each camera at a node can monitor its parent, itself, and its immediate children.
Return the minimum number of cameras needed to monitor all nodes of the tree.
Example 1:
Input: root = [0,0,null,0,0]
Output: 1
Explanation: One camera is enough to monitor all nodes if placed as shown.
Example 2:
Input: root = [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.
Constraints:
- The number of nodes in the tree is in the range
[1, 1000]. Node.val == 0
Solve it on LeetCode
Approaches
1. Recursive DFS Approach
Intuition:
In this problem, we need to cover all nodes of a binary tree with the minimum number of cameras. A straightforward brute force approach would be to consider placing a camera at every node, which clearly isn't efficient. Instead, we can use a recursive approach where we attempt to minimize the number of cameras required by deciding the optimal placement of each camera during the traversal of the tree.
We third introduce states for nodes:
0if the node is covered1if the node is monitored by a camera placed at one of its children2if the node has a camera
The base idea is:
- A leaf node would need a camera at its parent.
- A parent of a leaf can cover itself and the leaf if it has a camera.
- Each node decides whether it needs a camera based on whether its children are covered or need a camera.
Code:
- Time Complexity: O(N), where N is the number of nodes in the tree. Each node is visited once.
- Space Complexity: O(H), where H is the height of the tree due to the recursion stack.