华为5.20街道监控—java

题目描述
一个街区，为提高街区安全性，需在街区的路灯上安装若干摄像头，用一个二叉树表示街区的路灯，每个节点表示一个路灯，在路灯上安装摄像头。每个摄影头都可以监视其父对象、自身及其直接子对象。为保证每个路灯都被监控，请计算街区所需的最小摄像头数量。
输入描述:
输入一串字符，代表由前序排列的二叉树表示的路灯，字符由‘0’和‘#’组成，每个‘0’表示一个要监控路灯，‘#’表示子节点为空。
输出描述:
所需最小摄像头数量。
示例1输入输出示例仅供调试，后台判题数据一般不包含示例
输入
00##0#0
输出
2
说明
输入的路灯可以构建如下二叉树，1表示需要安装摄像头的路灯，输入的路灯数最少为2。
0
/
1 1

0
首先是要根据先序序列重构二叉树，然后就和leetcode 968这题一模一样了。
算法是要将每个节点的状态想清楚，分为3种状态，
0：没有被覆盖
1：被覆盖但是没装摄像头
2：装了摄像头（自身、左右孩子、父节点都被覆盖）。
所有节点初始时都时状态0，叶子节点不装摄像头。然后采用后序遍历的方式，从下到上，根据左右孩子节点的情况决定该节点是否要装摄像头。

import java.util.Scanner;

public class Three {

    public static int cameras = 0;
    public static int index = 0;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str = in.next();
        boolean matches = str.matches("[0#]+");
        if (!matches) {
            System.out.println("-1");
            return;
        }
        TreeNode root = null;
        TreeNode preOrder = preOrder(root, str);

        int rootState = minCameraCover(preOrder);
        if(rootState == 0) cameras++;
        System.out.println(cameras);
        in.close();
    }

    //前序遍历重新构造二叉树
    private static TreeNode preOrder(TreeNode root, String str) {
        // TODO Auto-generated method stub
        if(index>=str.length())
            return null;

        if (str.charAt(index)=='0') {
            root = new TreeNode(0);
            index++;
        }else {
            root = null;
            index++;
            return null;
        }
        root.left = preOrder(root.left, str);
        root.right = preOrder(root.right, str);
        return root;
    }

    //从下到上覆盖它--考虑新放置一个具有最深节点的相机，沿着树向上移动。

    //如果节点的子节点被覆盖，且该节点具有父节点，则最好的情况是将摄像机放置在父节点上。

    //每个节点有三种可能状态：
    //0：该节点没有被覆盖
    //1：该节点被覆盖，但是该节点没有摄像头
    //2：该节点有摄像头（它自身、左右孩子和父节点都被覆盖）
    //所有节点初始时都时状态0，叶子节点不装摄像头。然后采用后序遍历的方式，从下到上，根据左右孩子节点的情况决定该节点是否要装摄像头。
    public static int minCameraCover(TreeNode root) {
        if(root == null)
            return 1;
        int left = minCameraCover(root.left);
        int right = minCameraCover(root.right);
        //如果左右孩子存在没被覆盖的，该节点需要摄像头
        if(left == 0 || right == 0) {
            cameras++;
            return 2;
        }
        //如果左右孩子都被覆盖了，该节点返回没有被覆盖的状态
        if (left == 1&& right == 1) {
            return 0;
        }
        // 如果左右孩子存在装了摄像头的，那么该节点已经被覆盖了
        if (left + right >2) {
            return 1;
        }
        return -1;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        // TODO Auto-generated constructor stub
        this.val  =val;
    }
}