LeetCode [968] Binary Tree Cameras

 968. Binary Tree Cameras

Hard

Given a binary tree, we install cameras on the nodes of the tree. 

Each camera at a node can monitor its parent, itself, and its immediate children.

Calculate the minimum number of cameras needed to monitor all nodes of the tree.

 

Example 1:

Input: [0,0,null,0,0]
Output: 1
Explanation: One camera is enough to monitor all nodes if placed as shown.

Example 2:

Input: [0,0,null,0,null,0,null,null,0]
Output: 2
Explanation: At least two cameras are needed to monitor all nodes of the tree. The above image shows one of the valid configurations of camera placement.

Note:

1. The number of nodes in the given tree will be in the range [1, 1000].
2. Every node has value 0.

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 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { enum State { CAMERA, MONITORED, NOT_MONITORED } public int minCameraCover(TreeNode root) { Status status = getStatus(root); if (status.state == State.NOT_MONITORED) { status.cameras++; } return status.cameras; } private Status getStatus(TreeNode node) { if (node == null) return new Status(0, State.MONITORED); Status left = getStatus(node.left); Status right = getStatus(node.right); Status curr = new Status(left.cameras + right.cameras, State.NOT_MONITORED); if (left.state == State.NOT_MONITORED || right.state == State.NOT_MONITORED) { curr.cameras++; curr.state = State.CAMERA; } else if (left.state == State.CAMERA || right.state == State.CAMERA) { curr.state = State.MONITORED; } return curr; } private static class Status { int cameras; State state; Status(int cameras, State state) { this.cameras = cameras; this.state = state; } } }