package question;

/*
    @author: Roderland
    @create: 2020-09-22---16:01
*/
public class Question968 {
    public static void main(String[] args) {
        //[0,null,0,null,0,null,0]
        //[0,0,null,0,null,0,null,null,0]
        //[0,0,0,null,null,null,0,null,0]
        //[0,0,0,0,null,null,0,null,null,0]
        //[0,0,null,null,0,0,0,0,null,null,null,0]
        //[0,0,0,null,null,null,0,0,0,null,null,null,0,null,0]
        TreeNode t1 = new TreeNode(0);
        TreeNode t2 = new TreeNode(0);
        TreeNode t3 = new TreeNode(0);
        TreeNode t4 = new TreeNode(0);
        TreeNode t5 = new TreeNode(0);
        TreeNode t6 = new TreeNode(0);
        TreeNode t7 = new TreeNode(0);
        TreeNode t8 = new TreeNode(0);
        t1.left=t2;
        t1.right=t3;
        t3.right=t4;
        t4.left=t5;
        t4.right=t6;
        t6.right=t7;
        t7.right=t8;
        System.out.println(new Question968().minCameraCover(t1));
    }
    int count;
    public int minCameraCover(TreeNode root) {
        if (root==null) return 0;
        if (dfs(root)==2) count++;
        return count;
    }

    public int dfs(TreeNode root) {
        if (root==null) return 1;
        int left = dfs(root.left);
        int right = dfs(root.right);
        if (left==2||right==2) {
            count++;
            return 0;
        }
        if (left==0||right==0) {
            return 1;
        }
        return 2;
    }

}