侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【DFS】监控二叉树

GabrielxD
2022-05-19 / 0 评论 / 0 点赞 / 30 阅读 / 544 字 / 正在检测是否收录...

题目

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;
    }
}
0

评论区