监控二叉树

题目

给定一个二叉树，我们在树的节点上安装摄像头。

节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。

计算监控树的所有节点所需的最小摄像头数量。

思路

后序遍历，根据子节点的状态设置父节点的状态。若任一子节点未被监视，父节点则需安装摄像头；若任一子节点已安装摄像头，则父节点已被监视且无需安装；否则（子节点被子节点的子节点监视）返回其需要被监视。

代码

    int res = 0;

    public int minCameraCover(TreeNode root) {
        if (root == null) return 0;
        if (dfs(root) == -1)
            res++;
        return res;
    }

    // 1：该节点安装了摄像头
    // -1：未被监视
    // 0：被监视或为空
    private int dfs(TreeNode node) {
        if (node == null)
            return 0;
        int left = dfs(node.left);
        int right = dfs(node.right);
        if (left == -1 || right == -1) {
            res++;
            return 1;
        }
        if (left == 1 || right == 1)
            return 0;
        return -1;
    }