LeetCode 솔루션

[6/17] 968. Binary Tree Cameras

mingki 쪽지보내기 메일보내기 자기소개 아이디로 검색 전체게시물 작성
작성일 2022.06.16 19:17

6,714 조회
1 댓글
0 추천
0 비추천
목록 게시글 쓰기

Hard

280932Add to ListShare

You are given the root of a binary tree. We install cameras on the tree nodes where each camera at a node can monitor its parent, itself, and its immediate children.

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

Example 1:

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

Example 2:

Input: root = [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.

Constraints:

The number of nodes in the tree is in the range [1, 1000].
Node.val == 0

#Microsoft, #Google, #Quora, #DE Shaw, #eBay, #Bloomberg, #Amazon, #FactSet, #Apple, #Flipkart, #Facebook, #Dynamic Programming, #Tree, #Depth-First Search, #Binary Tree

링크

https://leetcode.com/problems/binary-tree-cameras/ 1505 회 연결

익명
작성일 2022.06.17 16:24

Runtime: 64 ms, faster than 55.43% of Python3 online submissions for Binary Tree Cameras.
Memory Usage: 14.2 MB, less than 92.33% of Python3 online submissions for Binary Tree Cameras.

# 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: Optional[TreeNode]) -> int:
        cameras = 0
        
        
        # return val: camera, monitored T/F
        def dfs(node):
            nonlocal cameras
            
            if not node:
                return False, True
            
            cam_left, mon_left = dfs(node.left)
            cam_right, mon_right = dfs(node.right)
            
            camera, monitored = False, False
            
            if cam_left or cam_right:
                monitored = True
            if not mon_left or not mon_right:
                camera = True
                cameras+=1
                monitored = True
            
            return camera, monitored
        
        camera, monitored = dfs(root)
        if not monitored: return cameras+1
        return cameras

Runtime: 64 ms, faster than 55.43% of Python3 online submissions for Binary Tree Cameras.
Memory Usage: 14.2 MB, less than 92.33% of Python3 online submissions for Binary Tree Cameras.

[code=Python 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: Optional[TreeNode]) -> int:
        cameras = 0
        
        
        # return val: camera, monitored T/F
        def dfs(node):
            nonlocal cameras
            
            if not node:
                return False, True
            
            cam_left, mon_left = dfs(node.left)
            cam_right, mon_right = dfs(node.right)
            
            camera, monitored = False, False
            
            if cam_left or cam_right:
                monitored = True
            if not mon_left or not mon_right:
                camera = True
                cameras+=1
                monitored = True
            
            return camera, monitored
        
        camera, monitored = dfs(root)
        if not monitored: return cameras+1
        return cameras[/code]