199. Binary Tree Right Side View

Binary Tree Right Side View - LeetCode

1. Queue를 이용한 풀이

class Solution:
    def rightSideView(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        answer, trace = [], defaultdict(int)
        q = deque([(root, 0)])
        while q:
            cur_node, cur_level = q.popleft()
            trace[cur_level] = cur_node.val
            if cur_node.left:
                q.append((cur_node.left, cur_level + 1))
            if cur_node.right:
                q.append((cur_node.right, cur_level + 1))
        for level in trace:
            answer.append(trace[level])
        return answer

트리를 오른쪽에서 보았을 때 보이는 노드를 레벨 순서대로 출력해 반환하는 문제다.

단순히 노드의 오른쪽으로만 탐색을 들어가면  [ 1, 2, 3, null, null, 4, null ]과 같은 케이스를 잡아내지 못하기 때문에 양쪽을 다 보긴 해야 한다.