/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int minCameraCover(TreeNode root) {
        Solver solver = new Solver(root);
        solver.solve();
        return solver.getCameras();
    }
}

class Solver {
    int cameras;
    TreeNode root, top, mid, bottom;
    HashSet<TreeNode> visited = new HashSet<>();
    HashSet<TreeNode> covered = new HashSet<>();

    Solver(TreeNode root) {
        this.root = root;
    }

    public void solve() {
        for(;;) {
            descend();

            if (!isCovered(bottom)) {
                setCamera(mid, top);
            }

            if (mid == null) break;

            visited.add(bottom);
        }
    }

    public int getCameras() {
        return cameras;
    }

    private void descend() {
        top = mid = bottom = null;
        TreeNode current = root;

        while (current != null) {
            top = mid;
            mid = bottom;
            bottom = current;
            current = (current.left != null && !visited.contains(current.left))
                ? current.left
                : !visited.contains(current.right) ? current.right : null;
        }
    }

    private void setCamera(TreeNode mid, TreeNode top) {
        cameras++;
        setCovered(top);
        setCovered(mid);
        if (mid != null) {
            setCovered(mid.left);
            setCovered(mid.right);
        }
    }

    private void setCovered(TreeNode node) {
        if (node != null && !isCovered(node)) covered.add(node);
    }

    private boolean isCovered(TreeNode node) {
        return node != null && covered.contains(node);
    }
}