# 968. Binary Tree Cameras      • Time: $O(n)$
• Space: $O(h)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 class Solution { public: int minCameraCover(TreeNode* root) { vector ans = dfs(root); return min(ans, ans); } private: // 0 := all nodes below root are covered except root // 1 := all nodes below and including root are covered w/o camera here // 2 := all nodes below and including root are covered w/ camera here vector dfs(TreeNode* root) { if (!root) return {0, 0, 1000}; vector l = dfs(root->left); vector r = dfs(root->right); const int s0 = l + r; const int s1 = min(l + min(r, r), r + min(l, l)); const int s2 = 1 + min({l, l, l}) + min({r, r, r}); return {s0, s1, s2}; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 class Solution { public int minCameraCover(TreeNode root) { int[] ans = dfs(root); return Math.min(ans, ans); } // 0 := all nodes below root are covered except root // 1 := all nodes below and including root are covered w/o camera here // 2 := all nodes below and including root are covered w/ camera here private int[] dfs(TreeNode root) { if (root == null) return new int[] {0, 0, 1000}; int[] l = dfs(root.left); int[] r = dfs(root.right); final int s0 = l + r; final int s1 = Math.min(l + Math.min(r, r), r + Math.min(l, l)); final int s2 = 1 + Math.min(l, Math.min(l, l)) + Math.min(r, Math.min(r, r)); return new int[] { s0, s1, s2 }; } }