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
class Solution {
 public:
  int minCameraCover(TreeNode* root) {
    vector<int> ans = dfs(root);
    return min(ans[1], ans[2]);
  }

 private:
  // 0 := all the nodes below the root are covered except the root
  // 1 := all the nodes below and including the root are covered with no camera
  // 2 := all nodes below and including the root are covered with a camera
  vector<int> dfs(TreeNode* root) {
    if (root == nullptr)
      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 = min({l[0], l[1], l[2]}) +  //
                   min({r[0], r[1], r[2]}) + 1;
    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 the nodes below the root are covered except the root
  // 1 := all the nodes below and including the root are covered with no camera
  // 2 := all nodes below and including the root are covered with a camera
  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 = Math.min(l[0], Math.min(l[1], l[2])) + //
                   Math.min(r[0], Math.min(r[1], r[2])) + 1;

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