← 전체 회차
A-054● Day 542026.06.30mediumleetcode #199neetcode150

이진 트리 우측 뷰

#tree#depth-first-search#breadth-first-search#binary-tree
↗ leetcode #199 · binary-tree-right-side-view
01

문제

· problem
P.054

이진 트리 우측 뷰

↗ leetcode #199

이진 트리의 루트가 주어졌을 때, 트리의 우측에 서 있는 자신을 상상하고, 위에서 아래로 순서대로 볼 수 있는 노드의 값들을 반환하세요.

제약
  • · The number of nodes in the tree is in the range [0, 100]
  • · -100 ≤ Node.val ≤ 100
// 지문은 본인 언어 요약 — 원문은 위 링크에서
입출력 예시
example 1input → output
[1,2,3,null,5,null,4]
[1,3,4]
example 2input → output
[1,2,3,4,null,null,null,5]
[1,3,4,5]
example 3input → output
[1,null,3]
[1,3]
example 4input → output
[]
[]
02

사전 사고

· pre-solve
● 1리스트 출력→● 2선택→● 3정답 공개
  • ☐
    우측 뷰는 우측 자식이 없는 노드들을 의미하나요?
  • ☐
    BFS와 DFS 중 어느 것을 사용해야 하나요?
  • ☐
    빈 트리일 경우 어떻게 처리하나요?
  • ☐
    우측 서브트리만 탐색하면 되나요?
  • ☐
    현재 레벨의 노드 개수를 알아야 하는 이유는 무엇인가요?
  • ☐
    각 레벨에서 우측 노드를 어떻게 찾나요?
  • ☐
    null 노드도 큐에 추가하나요?
던질 질문에 체크하고 확인을 누르세요
// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)
03

논리 구조

· logic
● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개
// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.
step 1· 결과 리스트 초기화
○
res = []
○
res = None
○
res = {}
step 2· 루트로 큐 초기화
○
q = collections.deque([root])
○
q = [root]
○
q = collections.deque()
step 3· 각 레벨을 반복 처리
○
while q:
○
if q:
○
while len(q) > 1:
step 4· 현재 레벨 설정│ 중첩
○
qLen = len(q)
○
qLen = q.maxlen; rightSide = 0
○
qLen = len(q) - 1
step 5· 현재 레벨의 모든 노드 순회│ 중첩
○
for i in range(qLen):
○
for node in q:
○
for i in range(qLen + 1):
step 6· 노드 처리 및 우측 추적│ │ 중첩
○
node = q.popleft()
○
rightSide = node
q.append(node.left)
q.append(node.right)
○
if node:
                    rightSide = node
step 7· 우측 노드값을 결과에 추가│ 중첩
○
if rightSide:
○
res.append(rightSide)
○
res.append(rightSide) if rightSide else pass
각 슬롯에 한 줄씩 골라보세요
// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.
04

문제풀이 · 트레이스

· solve
solution.py
1
# Definition for a binary tree node.
2
# class TreeNode:
3
#     def __init__(self, val=0, left=None, right=None):
4
#         self.val = val
5
#         self.left = left
6
#         self.right = right
7
class Solution:
8
    def rightSideView(self, root: TreeNode) -> List[int]:
9
        res = []
10
        q = collections.deque([root])
11
12
        while q:
13
            rightSide = None
14
            qLen = len(q)
15
16
            for i in range(qLen):
17
                node = q.popleft()
18
                if node:
19
                    rightSide = node
20
                    q.append(node.left)
21
                    q.append(node.right)
22
            if rightSide:
23
                res.append(rightSide.val)
24
        return res
머릿속 dry-run 케이스
// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.
case 1
[1,2,3,null,5,null,4]
→
[1,3,4]
case 2
[1,2,3,4,null,null,null,5]
→
[1,3,4,5]
case 3
[1,null,3]
→
[1,3]
case 4
[]
→
[]
// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.