[DSA][Trees] 09. Binary Tree Right Side View

LeetCode 199

 

09. 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가 null일 경우 빈 리스트를 반환하나요?

 

[아이디어]

- BFS 방식으로 트리를 순회하면서, 각 노드를 큐(deque)에 저장해 레벨 단위로 탐색한다.

 

 

[풀이 1] Breadth First Search

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        
        res = []
        q = deque()
        q.append(root)
        while q:
            tmp = []
            for i in range(len(q)):
                node = q.popleft()
                tmp.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            res.append(tmp[-1])
        
        return res

문제의 접근법은 Binary Tree Level Order Traversal 문제에서와 비슷하게 BFS(너비 우선 탐색)를 사용하는 것이다.

2025.07.17 - [자료구조와 알고리즘] - [DSA][Trees] 08. Binary Tree Level Order Traversal

다만, 차이점은 각 레벨의 마지막 노드만을 저장하면 된다는 점이다. 해당 문제의 풀이와 비교해 보면,동일한 코드에서 tmp 대신 tmp[-1]을 저장하였다.

 

⏱️ 시간복잡도

트리의 모든 노드를 한 번씩 방문하므로, 시간 복잡도는 O(n)이다.

🧠 공간복잡도

큐에 각 레벨의 노드를 저장하므로  O(n)의 공간 복잡도를 가진다.