Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/968.html
968. Binary Tree Cameras (Hard)
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:
- The number of nodes in the given tree will be in the range
[1, 1000]
. - Every node has value 0.
Companies:
Facebook
Related Topics:
Dynamic Programming, Tree, Depth-first Search
Solution 1.
Assumption: we can alter the value of the tree node.
Use postorder traversal. Let val
convey the state of the node:
- 0 means uncovered.
- 1 means covered
- 2 means having camera
If node
is NULL
, we regard it as 1
.
- If either of my left/right child is uncovered, I have to put a camera.
- Otherwise, if either of my left/right child has camera, I’m covered and skip me.
- Otherwise (both children are covered), if I’m root, I have to put a camera.
- Otherwise, skip me.
// OJ: https://leetcode.com/problems/binary-tree-cameras/
// Time: O(N)
// Space: O(logN)
class Solution {
private:
TreeNode *R;
int postorder(TreeNode* root) {
if (!root) return 0;
int ans = postorder(root->left) + postorder(root->right);
int left = root->left ? root->left->val : 1;
int right = root->right ? root->right->val : 1;
if (left == 0 || right == 0) {
root->val = 2;
return ans + 1;
} else if (left == 2 || right == 2) {
root->val = 1;
return ans;
} else return root == R ? ans + 1 : ans;
}
public:
int minCameraCover(TreeNode* root) {
R = root;
return postorder(root);
}
};
Solution 2.
If we can’t have the assumption in Solution 1, we can use the return value to return my state to my parent.
// OJ: https://leetcode.com/problems/binary-tree-cameras/
// Time: O(N)
// Space: O(logN)
class Solution {
private:
int ans = 0;
int postorder(TreeNode *root) {
if (!root) return 1;
int left = postorder(root->left);
int right = postorder(root->right);
if (left == 0 || right == 0) {
++ans;
return 2;
} else return left == 2 || right == 2 ? 1 : 0;
}
public:
int minCameraCover(TreeNode* root) {
return postorder(root) == 0 ? ans + 1 : ans;
}
};
-
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public int minCameraCover(TreeNode root) { if (root == null) return 0; List<TreeNode> list = new ArrayList<TreeNode>(); Queue<TreeNode> queue = new LinkedList<TreeNode>(); queue.offer(root); while (!queue.isEmpty()) { TreeNode node = queue.poll(); list.add(node); TreeNode left = node.left, right = node.right; if (left != null) queue.offer(left); if (right != null) queue.offer(right); } Map<TreeNode, int[]> map = new HashMap<TreeNode, int[]>(); for (int i = list.size() - 1; i >= 0; i--) { TreeNode node = list.get(i); if (node.left == null && node.right == null) map.put(node, new int[]{0, Integer.MAX_VALUE / 10, 1}); else if (node.left == null) { int[] rightArray = map.get(node.right); int[] array = new int[3]; array[0] = rightArray[1]; array[1] = rightArray[2]; array[2] = 1 + Math.min(rightArray[0], Math.min(rightArray[1], rightArray[2])); map.put(node, array); } else if (node.right == null) { int[] leftArray = map.get(node.left); int[] array = new int[3]; array[0] = leftArray[1]; array[1] = leftArray[2]; array[2] = 1 + Math.min(leftArray[0], Math.min(leftArray[1], leftArray[2])); map.put(node, array); } else { int[] leftArray = map.get(node.left); int[] rightArray = map.get(node.right); int minLeft = Math.min(leftArray[1], leftArray[2]); int minRight = Math.min(rightArray[1], rightArray[2]); int[] array = new int[3]; array[0] = leftArray[1] + rightArray[1]; array[1] = Math.min(leftArray[2] + minRight, rightArray[2] + minLeft); array[2] = 1 + Math.min(leftArray[0], minLeft) + Math.min(rightArray[0], minRight); map.put(node, array); } } int[] rootArray = map.get(root); return Math.min(rootArray[1], rootArray[2]); } } ############ /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { private int ans; public int minCameraCover(TreeNode root) { ans = 0; return (dfs(root) == 0) ? ans + 1 : ans; } private int dfs(TreeNode root) { if (root == null) { return 2; } int left = dfs(root.left); int right = dfs(root.right); if (left == 0 || right == 0) { ++ans; return 1; } if (left == 1 || right == 1) { return 2; } return 0; } }
-
// OJ: https://leetcode.com/problems/binary-tree-cameras/ // Time: O(N) // Space: O(logN) class Solution { private: TreeNode *R; int postorder(TreeNode* root) { if (!root) return 0; int ans = postorder(root->left) + postorder(root->right); int left = root->left ? root->left->val : 1; int right = root->right ? root->right->val : 1; if (left == 0 || right == 0) { root->val = 2; return ans + 1; } else if (left == 2 || right == 2) { root->val = 1; return ans; } else return root == R ? ans + 1 : ans; } public: int minCameraCover(TreeNode* root) { R = root; return postorder(root); } };
-
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def minCameraCover(self, root: TreeNode) -> int: def dfs(root): nonlocal ans if root is None: return 2 left, right = dfs(root.left), dfs(root.right) if left == 0 or right == 0: ans += 1 return 1 return 2 if left == 1 or right == 1 else 0 ans = 0 return (dfs(root) == 0) + ans ############ # 968. Binary Tree Cameras # https://leetcode.com/problems/binary-tree-cameras/ # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def minCameraCover(self, root: Optional[TreeNode]) -> int: res = 0 def go(node): nonlocal res if not node: return 2 left, right = go(node.left), go(node.right) if left == 0 or right == 0: res += 1 return 1 return 2 if left == 1 or right == 1 else 0 return (go(root) == 0) + res
-
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func minCameraCover(root *TreeNode) int { ans := 0 var dfs func(root *TreeNode) int dfs = func(root *TreeNode) int { if root == nil { return 2 } left, right := dfs(root.Left), dfs(root.Right) if left == 0 || right == 0 { ans++ return 1 } if left == 1 || right == 1 { return 2 } return 0 } if dfs(root) == 0 { return ans + 1 } return ans }
-
/** * Definition for a binary tree node. * class TreeNode { * val: number * left: TreeNode | null * right: TreeNode | null * constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } * } */ function minCameraCover(root: TreeNode | null): number { const dfs = (root: TreeNode | null): number[] => { if (!root) { return [1 << 29, 0, 0]; } const [la, lb, lc] = dfs(root.left); const [ra, rb, rc] = dfs(root.right); const a = 1 + Math.min(la, lb, lc) + Math.min(ra, rb, rc); const b = Math.min(la + ra, la + rb, lb + ra); const c = lb + rb; return [a, b, c]; }; const [a, b, _] = dfs(root); return Math.min(a, b); }