0968._Binary_Tree_Cameras.md

968. Binary Tree Cameras

难度: Hard

刷题内容

原题连接

• https://leetcode.com/problems/binary-tree-cameras/

内容描述

Given a binary tree, we install cameras on the nodes of the tree. 

Each camera at a node can monitor its parent, itself, and its immediate children.

Calculate the minimum number of cameras needed to monitor all nodes of the tree.

 

Example 1:


Input: [0,0,null,0,0]
Output: 1
Explanation: One camera is enough to monitor all nodes if placed as shown.
Example 2:


Input: [0,0,null,0,null,0,null,null,0]
Output: 2
Explanation: At least two cameras are needed to monitor all nodes of the tree. The above image shows one of the valid configurations of camera placement.

解题方案

思路 1 - 时间复杂度: O(N)- 空间复杂度: O(1)******

直接看的答案

class Solution:
    def minCameraCover(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        # Return 0 if it's a leaf.
        # Return 1 if it's a parent of a leaf, with a camera on this node.
        # Return 2 if it's coverd, without a camera on this node.
        self.res = 0
        def dfs(root):
            if not root: # 不是一个点不可能返回0，上面也没有camera不可能返回1
                return 2
            l, r = dfs(root.left), dfs(root.right)
            if l == 0 or r == 0: # 任意一个child是leaf, root作为它的parent必须要放camera
                self.res += 1
                return 1
            if l == 1 or r == 1: # 任意一个child上有camera, root就被cover了
                return 2
            return 0 # 只剩下一种情况了，即 l == 2 and r == 2，说明root被下面所有点孤立了，即新的leaf
        return (dfs(root) == 0) + self.res