Solution: Binary Tree Cameras
Statement▼
You are given the root of a binary tree. Cameras can be installed on any node, and each camera can monitor itself, its parent, and its immediate children.
Your task is to determine the minimum number of cameras required to monitor every node in the tree.
Constraints:
The number of nodes in the tree is in the range
[1,1000] .Node.data==0
Solution
Each node in the tree can be in one of three possible states, based on how it's monitored:
State 0 (Not covered): All the nodes below this node are monitored, but this node is not.
State 1 (Covered, no camera): All the nodes below, including this node, are monitored, but there is no camera at this node.
State 2 (Has camera): A camera is installed at this node, monitoring itself, its parent, and its immediate children.
We don’t need to track the exact configuration of the entire tree. Instead, we only need to evaluate the local coverage status of each node and make decisions accordingly. We traverse the tree in post-order, first computing values for the left and right children and using them to decide the optimal state for the current node.
At each node, we compute the minimum number of cameras required for each of the three states:
State 0: This requires both children to be in state 1 (i.e., they are covered, but without cameras).
State 1: At least one child must have a camera (state 2), and the other can be in either state 1 or 2. This way, the current node is covered by its ...
Solution: Binary Tree Cameras
Statement▼
You are given the root of a binary tree. Cameras can be installed on any node, and each camera can monitor itself, its parent, and its immediate children.
Your task is to determine the minimum number of cameras required to monitor every node in the tree.
Constraints:
The number of nodes in the tree is in the range
[1,1000] .Node.data==0
Solution
Each node in the tree can be in one of three possible states, based on how it's monitored:
State 0 (Not covered): All the nodes below this node are monitored, but this node is not.
State 1 (Covered, no camera): All the nodes below, including this node, are monitored, but there is no camera at this node.
State 2 (Has camera): A camera is installed at this node, monitoring itself, its parent, and its immediate children.
We don’t need to track the exact configuration of the entire tree. Instead, we only need to evaluate the local coverage status of each node and make decisions accordingly. We traverse the tree in post-order, first computing values for the left and right children and using them to decide the optimal state for the current node.
At each node, we compute the minimum number of cameras required for each of the three states:
State 0: This requires both children to be in state 1 (i.e., they are covered, but without cameras).
State 1: At least one child must have a camera (state 2), and the other can be in either state 1 or 2. This way, the current node is covered by its ...