Note
이진 트리를 오른쪽에서 봤을 때 보이는 노드는, 각 레벨마다 가장 오른쪽에 있는 노드입니다. 레벨 순서 BFS로 각 레벨의 마지막 노드를 모으면 됩니다.
문제 상황
이진 트리의 root가 주어졌을 때, 트리를 오른쪽에서 봤을 때 보이는 노드들의 값을 위에서부터 순서대로 반환합니다.
- 같은 레벨에 여러 노드가 있으면 오른쪽에 있는 노드만 보임
- 레벨이 다르면 각 레벨에서 하나씩 보임
따라서 각 레벨에서 가장 오른쪽 노드를 모두 모은 것이 정답입니다.
핵심 아이디어: 레벨 순서 BFS + “레벨의 마지막 노드”
**BFS(너비 우선 탐색)**로 노드를 레벨별로, 왼쪽→오른쪽 순서로 방문하면:
- 한 레벨을 다 처리할 때마다, 마지막으로 방문한 노드가 그 레벨의 가장 오른쪽 노드
- 이 노드의 값만 수집하면 “오른쪽에서 본 값”이 됨
즉, 레벨 구분이 있는 BFS를 하고, 각 레벨이 끝날 때마다 마지막 노드의 값을 결과에 넣으면 됩니다.
레벨 구분 BFS 두 가지 방식
1. 두 개의 큐 (현재 레벨 / 다음 레벨)
- queue: 현재 레벨 노드들
- next_queue: 그 자식들(다음 레벨)
현재 레벨에서 노드를 하나씩 꺼내면서:
- 자식을 next_queue에 넣음
- queue가 비면 → 방금 꺼낸 노드가 그 레벨의 마지막 노드 → 값 기록
그다음queue = next_queue,next_queue비우고 반복
2. 한 큐 + 레벨 크기
- 큐에 노드를 넣을 때 같은 레벨의 노드 개수를 알고 있으면, 그 개수만큼만 popleft 했을 때의 마지막 노드가 레벨의 오른쪽 끝
level_size = len(queue)로 한 레벨씩 처리하고, 매 레벨의 마지막 노드만 결과에 추가
둘 다 시간 O(n), 공간 O(n) 이고, “레벨의 마지막 = 오른쪽에서 보이는 노드”라는 점은 동일합니다.
예시
1 ← 레벨 0: 오른쪽 끝 = 1
/ \
2 3 ← 레벨 1: 오른쪽 끝 = 3
\ \
5 4 ← 레벨 2: 오른쪽 끝 = 4
BFS 순서(왼→오): 레벨0 [1], 레벨1 [2,3], 레벨2 [5,4]
각 레벨의 마지막: 1, 3, 4 → Right Side View = [1, 3, 4]
요약
| 항목 | 내용 |
|---|---|
| “오른쪽에서 본다” | 각 레벨에서 가장 오른쪽 노드만 보임 |
| 방법 | 레벨 순서 BFS (왼쪽→오른쪽) |
| 수집 | 각 레벨을 끝낼 때, 그 레벨에서 마지막으로 방문한 노드의 값 |