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
|
class Solution { public int minCameraCover(TreeNode root) { return Math.min(minCam(root, true, true), minCam(root, false, false)); } private int minCam(TreeNode root, boolean hasCamera, boolean isWatched){ if(root == null) return hasCamera ? Integer.MAX_VALUE / 2 : 0;
if(hasCamera){ int min = Math.min(minCam(root.left, false, true) + minCam(root.right, false, true), minCam(root.left, true, true) + minCam(root.right, false, true)); min = Math.min(min, minCam(root.left, false, true) + minCam(root.right, true, true)); return 1 + min; } else if(isWatched){ int min = Math.min(minCam(root.left, true, true) + minCam(root.right, true, true), minCam(root.left, true, true) + minCam(root.right, false, false)); min = Math.min(min, minCam(root.left, false, false) + minCam(root.right, true, true)); min = Math.min(min, minCam(root.left, false, false) + minCam(root.right, false, false)); return min; } else{ int min = Math.min(minCam(root.left, true, true) + minCam(root.right, true, true), minCam(root.left, true, true) + minCam(root.right, false, false)); min = Math.min(min, minCam(root.left, false, false) + minCam(root.right, true, true)); return min; } } }
|