968. Binary Tree Cameras

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
/**
 * Refer:
 * https://leetcode.com/problems/binary-tree-cameras/discuss/211180/JavaC++Python-Greedy-DFS
 *
 * Time Complexity: O(N)
 *
 * Space Complexity: O(N)
 *
 * N = Number of node in the tree.
 */
class Solution {
    public int minCameraCover(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int[] count = new int[1];
        int finalState = dfsHelper(root, count);
        if (finalState == 0) {
            count[0]++;
        }

        return count[0];
    }

    // State 0 = Uncovered
    // State 1 = Covered and Camera Here
    // State 2 = Covered and Camera NOT Here
    // For NULL... Since there is no node, its covered but there is no camera.
    private int dfsHelper(TreeNode node, int[] count) {
        if (node == null) {
            return 2;
        }

        int left = dfsHelper(node.left, count);
        int right = dfsHelper(node.right, count);

        if (left == 0 || right == 0) {
            count[0]++;
            return 1;
        }
        if (left == 1 || right == 1) {
            return 2;
        }
        return 0;
    }
}