968. 监控二叉树

Difficulty
Hard
Tags
二叉树
URL
https://leetcode-cn.com/problems/binary-tree-cameras/
Star
给定一个二叉树，我们在树的节点上安装摄像头。
节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
计算监控树的所有节点所需的最小摄像头数量。
示例 1：
notion imagenotion image
输入：[0,0,null,0,0]
输出：1
解释：如图所示，一台摄像头足以监控所有节点。
示例 2：
notion imagenotion image
输入：[0,0,null,0,null,0,null,null,0]
输出：2
解释：需要至少两个摄像头来监视树的所有节点。 上图显示了摄像头放置的有效位置之一。
提示：
  1. 给定树的节点数的范围是 [1, 1000]。
  1. 每个节点的值都是 0。
通过次数33,720提交次数66,108

法 1 信息传递

思路
二叉树有3种遍历，那就有3种信息交流的方式，前序的自上而下，后序的自下而上，中序的左上右下，根据题目要求，这题选用后续遍历是传递信息的最佳选择。需要传递的信息有三种：1.要求父节点安装相机；2.说自己有相机；3.自己不需要相机或空节点；那么，每个节点在接受了两个子节点的信息后，还要判断自己要向父节点传递哪种信息，如此层层向上传递，便解决了问题。
题解
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def minCameraCover(self, root: TreeNode) -> int:
        if root is None:
            return 0
        self.res = 0
        if self.dfs(root) == 2:
            print("1")
            self.res += 1
        
        return self.res

    # 返回 3 种状态， 0：自己安装了监控器， 1:自己没装，也不需要； 2：要求父节点装
    def dfs(self, node):
        if node is None:
            return 1

        l = self.dfs(node.left)
        r = self.dfs(node.right)
				# 当前节点需要装摄像头
        if l == 2 or r == 2: 
            self.res += 1
            return 0
				# 
        if l == 0 or r == 0:
            return 1
        

        return 2