엔지니어 게시판
LeetCode 솔루션 분류

[6/17] 968. Binary Tree Cameras

컨텐츠 정보

본문

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

관련자료

댓글 1

학부유학생님의 댓글

  • 익명
  • 작성일
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
전체 396 / 1 페이지
번호
제목
이름

최근글


인기글


새댓글


Stats


  • 현재 접속자 223 명
  • 오늘 방문자 19 명
  • 어제 방문자 6,462 명
  • 최대 방문자 11,134 명
  • 전체 회원수 1,049 명
알림 0