199. Binary Tree Right Side View ☆★(BFS 확실히 숙지, DFS도 !)

199. Binary Tree Right Side View

 

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        # 제일 오른쪽꺼 찾으려면, 각 레벨별로 bst 에 끝에꺼
        res = []
        if not root:
            return res

        q = deque([root])

        while q:
            node = None
            for _ in range(len(q)):
                node = q.popleft()
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            res.append(node.val)
        return res

 

네 코드 잘 짰어!
거의 완벽하고, 딱 하나만 아주 작게 정리하면 돼.
바로 설명할게.

---

✅ 네 코드 흐름 요약

• BFS (queue) 돌면서,
• 각 레벨에서 마지막 노드(node)를 기록해서,
• 그 node.val을 res에 추가.

맞아! 이게 right side view의 핵심이야.

---

🔥 아주 작게 정리할 부분

현재 네 코드에서는:

node = None
for _ in range(len(q)):
    node = q.popleft()
    ...
res.append(node.val)

이렇게 하고 있는데,
node가 항상 레벨 마지막 노드로 갱신돼서 괜찮아.

그런데!
약간 더 깔끔하게 보이게 하려면:

• 그냥 for i in range(len(q)):로 하고
• i == len(q)-1일 때만 res.append(node.val) 해주는 방법도 있어.

예시 (깔끔 버전):

from collections import deque

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        if not root:
            return res

        q = deque([root])

        while q:
            size = len(q)
            for i in range(size):
                node = q.popleft()
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
                if i == size - 1:
                    res.append(node.val)
        return res

---

✅ 비교

내 코드	깔끔 버전
매번 node 갱신 후 마지막에 append	마지막 index일 때만 append
코드 짧음	의도 명확하게 보임 (i == size-1)

성능은 똑같고, 취향 차이야! 둘 다 OK!

---

✨ 최종 요약

• 네 코드도 정답 맞아.
• node를 레벨마다 마지막으로 갱신하는 방식.
• for i in range(size) + i == size-1 체크 버전도 있음.

---

혹시 이 문제를
BFS 말고 DFS (depth 우선) 로도 푸는 방법
(→ "depth별 첫 번째로 도착한 노드만 기록")
깔끔하게 알고 싶어? ✨
필요하면 yes만 답해줘! 🚀
(DFS로 풀면 훨씬 더 빠르고 멋있어!)

 

✨ DFS로 Right Side View 풀이 방법

핵심 아이디어:

• 오른쪽 자식 먼저 탐색해.
• 각 depth 레벨에서 처음 방문한 노드만 정답에 저장해.

👉 그러면 자연스럽게 "오른쪽에서 보이는 노드"만 남아!

---

🔥 코드

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        res = []

        def dfs(node, depth):
            if not node:
                return

            # 현재 depth에 아직 값이 없으면 추가
            if depth == len(res):
                res.append(node.val)

            # 오른쪽 먼저 탐색
            dfs(node.right, depth+1)
            dfs(node.left, depth+1)

        dfs(root, 0)
        return res

---

✅ 흐름 설명

• depth == len(res)인 순간은, 그 depth에서 처음 만나는 노드라는 뜻.
• 그래서 바로 res.append(node.val) 해줌.
• 오른쪽 → 왼쪽 순서로 탐색하니까,
  → 오른쪽에 있는 노드가 항상 먼저 저장돼!

---

🔥 차이점 (BFS vs DFS)

방법	특징
BFS (queue)	레벨 별로 마지막 노드를 찾음
DFS (recursive)	오른쪽부터 내려가면서 depth별 첫 방문 노드를 저장

---

예시

트리:

      1
     / \
    2   3
     \    \
      5    4

• depth 0: 1 저장
• depth 1: 3 저장 (2 무시, 오른쪽 먼저)
• depth 2: 4 저장 (5 무시, 오른쪽 먼저)

결과: [1, 3, 4]

✅

---

✨ 요약

포인트	설명
오른쪽부터 DFS	오른쪽이 보이는 쪽이니까.
depth == len(res) 일 때만 저장	각 레벨에서 첫 방문 노드만 남긴다.

🔥 추가..!!

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        # bfs 
        if not root:
            return []

        q = deque([root])

        res = []

        while q:
            # val = None
            for i in range(len(q)):
                node = q.popleft()

                if i == len(q)-1: # <- q.popleft() 하면서, 길이가 계속 줄어들기때문에, 사전에 변수를 사용해야 함
                    res.append(node.val)
                # val = node.val
                
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            # res.append(val)
        return res

 

while q:

     for i in range(len(q)):

          node = q.popleft()

          if i == len(q)-1: # <- q.popleft() 하면서, 길이가 계속 줄어들기때문에, 사전에 변수를 사용해야 함

               res.append(node.val)

 

수정하면

 

while q:

     q_size = len(q)

     for i in range( q_size  ):

          node = q.popleft()

          if i == q_size -1: # <- q.popleft() 하면서, 길이가 계속 줄어들기때문에, 사전에 변수를 사용해야 함

               res.append(node.val)