[Neetcode/Tree] Binary Tree Right Side View

https://neetcode.io/problems/binary-tree-right-side-view

NeetCode

첫번째 풀이 방법: BFS - Level Order Traversal

1. 각 레벨에서 가장 오른쪽에 있는 노드의 값만 저장하면 된다.
2. BFS(너비 우선 탐색, Queue;)을 이용하여 레벨별 탐색을 수행한다.
3. 매 레벨의 마지막 노드 값을 결과 리스트에 추가한다.

# 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]:
        if not root:
            return []

        result = []
        queue = deque([root])

        while queue:
            level_size = len(queue)

            for i in range(level_size):
                node = queue.popleft()
                
                # 각 레벨의 마지막 노드를 저장
                if i == level_size - 1:
                    result.append(node.val)
                
                # 오른쪽 자식을 먼저 넣음 (우선 탐색을 위해)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
                    
        return result

두번째 풀이 방법: DFS - 깊이 우선 탐색

• DFS를 사용할 경우, 각 깊이에서 처음 방문한 노드가 바로 오른쪽 노드이다. 따라서 이를 결과 리스트에 추가한다.

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

        def dfs(node, depth):
            if not node:
                return
            
            # 해당 깊이에 처음 도달한 경우, 오른쪽 뷰에서 보이는 노드
            if depth == len(result):
                result.append(node.val)
            
            # 오른쪽 -> 왼쪽 순서로 탐색 (우선적으로 오른쪽이 보이도록)
            dfs(node.right, depth + 1)
            dfs(node.left, depth + 1)

        dfs(root, 0)
        return result