968.监控二叉树

题目描述

题解

DFS

采取自下向上的思路, 顺序为后续遍历. 对于每个节点, 要根据其子节点的状态来判断是否要安装摄像头, 定义三个状态来描述每个节点:

0: 该节点待覆盖. 当该节点为叶子节点或者两个儿子都被覆盖但是两个儿子都没有安装相机时

1: 该节点被覆盖. 至少有一个儿子有相机或者该节点为null时.

2: 该节点安装相机. 当两个儿子都是状态0时

class Solution {
    int count = 0;

    public int minCameraCover(TreeNode root) {
        if (dfs(root) == 0) {
            count++;
        }
        return count;
    }


    private int dfs(TreeNode root) {
        if (root == null) {
            return 1;
        }

        int left = dfs(root.left);
        int right = dfs(root.right);

        if (left == 1 && right == 1) {
            return 0;
        } else if (left == 0 || right == 0) {
            count++;
            return 2;
        } else if (left + right >= 3) {
            return 1;
        }

        return -1;

    }
}