[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);
    }
}

Author: huadonghu

Leave a Reply

Your email address will not be published. Required fields are marked *