LeetCode: 968. Binary Tree Cameras

어렵다...

Greedy한 접근법이 필요하다.

내 머리론 못 풀었고, 아래 풀이를 바탕으로 코드를 작성했다.

https://leetcode.com/problems/binary-tree-cameras/discuss/211180/JavaC%2B%2BPython-Greedy-DFS

[Java/C++/Python] Greedy DFS - LeetCode Discuss

핵심은 아래와 같다.

- Leaf Node에 카메라를 둘 이유가 전혀 없다. Leaf의 parent에 카메라를 두는 것이 무조건 더 효율적이다. 때문에 Greedy한 접근이 필요하다.

- DFS로 순회하면서 각 Node를 Tri-state로 표현해준다. Node는 자기 자식에 의해 'covered' 되었거나, 'to be covered'이거나, 카메라를 갖는 'covering' 세가지 상태로 표현한다. 모든 node는 총 9가지 case가 나온다(왼쪽자식 3개 * 오른쪽 자식 3개). 각 case에 대해 논리적으로 생각해보면 아래 코드가 나온다.

- corner case로 None node에 'covered'를 부여하면 모든 node가 자식을 2개 갖는 것처럼 다룰 수 있다. 

# 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:
        self.ret = 0
        root_state = self.dfs(root)
        if root_state == 'should be covered':
            return self.ret + 1
        return self.ret
        
    def dfs(self, node):
        if not node:
            return 'covered'
        l, r = self.dfs(node.left), self.dfs(node.right)
        if l == 'should be covered' or r == 'should be covered':
            self.ret += 1
            return 'covering'
        if l == 'covering' or r == 'covering':
            return 'covered'
        return 'should be covered'