# [LeetCode] 968. Binary Tree Cameras

## Solution

This problem can be reduced to Minimum Dominating Set problem in Trees. Find minimum set of vertices such that every vertex is in or adjacent to set is NP-complete in general graphs, but polynomial time on trees.

The following is adopted from MIT’s lectures.

## Code

``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
class Node {
int s;  //select
int ns; //not select
int nsc;//not select of Childresn
Node left;
Node right;
Node(int s, int ns, int nsc) {
this.s = s;
this.ns = ns;
this.nsc = nsc;
}
}
private int count = 0;
public int minCameraCover(TreeNode root) {
Node dp = _cloneTree(root);
traversal(dp);
return dp.s;
}

private Node _cloneTree(TreeNode root) {
if (root == null) {
return null;
}
Node dp = new Node(0, 0,0);
count++;
dp.left = _cloneTree(root.left);
dp.right = _cloneTree(root.right);
return dp;
}

private void traversal(Node root) {
if (root == null) {
return;
}
if (root.left == null && root.right == null) {
root.s = 1;
root.ns = 0;
root.nsc = 0;
//System.out.printf("%d %d %d\n",root.s, root.ns, root.nsc);
return;
}
if (root.left != null) {
traversal(root.left);
}
if (root.right != null) {
traversal(root.right);
}

if (root.left == null) {
root.ns = Math.min(1+root.right.ns, root.right.s);
} else if (root.right == null) {
root.ns = Math.min(1+root.left.ns, root.left.s);
}else {
root.ns = Math.min(1+root.left.ns + root.right.ns, root.left.s + root.right.s);
}

if (root.left == null) {
root.s = Math.min(1 + root.right.ns, 1 + root.right.nsc);
} else if (root.right == null) {
root.s = Math.min(1 + root.left.ns, 1 + root.left.nsc);
} else {
root.s = Math.min(1 + root.left.ns + root.right.ns, Math.min(1 + root.left.nsc + root.right.s, 1 + root.right.nsc + root.left.s ));
}

if (root.left == null) {
root.nsc = root.right.ns;
} else if (root.right == null) {
root.nsc = root.left.ns;
} else {
root.nsc = root.left.ns + root.right.ns;
}
//System.out.printf("%d %d %d\n",root.dp, root.dpN, root.dpNS);
}
}``````