【DFS】监控二叉树

题目

968. 监控二叉树

---

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

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

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

示例 1：

输入：[0,0,null,0,0]
输出：1
解释：如图所示，一台摄像头足以监控所有节点。

示例 2：

输入：[0,0,null,0,null,0,null,null,0]
输出：2
解释：需要至少两个摄像头来监视树的所有节点。 上图显示了摄像头放置的有效位置之一。

提示：

• 给定树的节点数的范围是 [1, 1000]。
• 每个节点的值都是 0。

解题

方法一：DFS

思路

对于每个节点，它有三个状态中的一种：0 : 该节点未被监控，1 : 该节点被监控，但它不是摄像头，2 : 该节点是摄像头。 对于每个节点：

• 如果该节点不存在，为了防止其被误判，把他置为状态 1
• 递归地求出该节点左右子节点的状态。
• 如果两个孩子节点都是状态 0 即未被监控，则在当前节点上装监控并把摄像头数量自增，返回当前节点的状态 2。
• 如果有一个子节点的状态是 2 即是摄像头，则当前节点应该被监控了，返回当前节点的状态 1。
• 其它情况下，当前节点未被监控，但也不需要在当前节点上装摄像头，返回当前节点的状态 0。

特例：当树不为空但一个摄像头都没装是不合理的，怎么说都要装一个。

代码

class Solution {
    private int ans = 0;

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

    private int dfs(TreeNode node) {
        if (node == null) return 1;
        int left = dfs(node.left), right = dfs(node.right);
        if (left == 0 || right == 0) {
            ans++;
            return 2;
        } else if (left == 2 || right == 2) return 1;
        else return 0;
    }
}