Skip to content

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<int> ans = dfs(root);
    return min(ans[1], ans[2]);
  }

 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<int> dfs(TreeNode* root) {
    if (!root)
      return {0, 0, 1000};

    vector<int> l = dfs(root->left);
    vector<int> r = dfs(root->right);

    const int s0 = l[1] + r[1];
    const int s1 = min(l[2] + min(r[1], r[2]),
                       r[2] + min(l[1], l[2]));
    const int s2 = 1 + min({l[0], l[1], l[2]}) +
                       min({r[0], r[1], r[2]});

    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[1], ans[2]);
  }

  // 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[1] + r[1];
    final int s1 = Math.min(l[2] + Math.min(r[1], r[2]),
                            r[2] + Math.min(l[1], l[2]));
    final int s2 = 1 + Math.min(l[0], Math.min(l[1], l[2])) +
                       Math.min(r[0], Math.min(r[1], r[2]));

    return new int[] { s0, s1, s2 };
  }
}