[LeetCode 해석 및 풀이] 199. Binary Tree Right Side View(이진 트리 오른쪽 보기)

LeetCode 문제 해석 및 풀이 방법

문제 199. Binary Tree Right Side View(이진 트리 오른쪽 보기)

난이도 : 중간🟡 바로가기

 

문제 설명

영문

Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

 

한글

이진 트리의 root 주어지면 자신이 그 오른쪽에 서 있다고 상상하고 위에서 아래로 정렬된 노드 값을 반환합니다.

 

제한조건

• The number of nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100

 

입출력 예

입력	출력
root = [1,2,3,null,5,null,4]	[1,3,4]
root = [1,null,3]	[1,3]
root = []	[]

 

해답 및 해설

파이썬 (Python)

from queue import Queue

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
 
        answer = []
        queue_now = Queue()
        queue_now.put(root)
        queue_future = Queue()
 
        while not queue_now.empty():
            while not queue_now.empty():
                now_node = queue_now.get()
 
                if now_node.left:
                    queue_future.put(now_node.left)
                if now_node.right:
                    queue_future.put(now_node.right)
            
            answer.append(now_node.val)
            queue_now, queue_future = queue_future, queue_now
        
        return answer

 

언뜻 생각하면 오른쪽 가지만 보면 될 것 같지만, 오른쪽 가지가 왼쪽 가지보다 짧은 경우도 생각해야 되어서 그렇지가 않다.

 

102. Binary Tree Level Order Traversal 문제에서 너비 우선 탐색을 했던 방식을 살짝 변형하여 각 레벨의 끝일 때 값을 추가해주는 방식을 이용하였다.