[LeetCode] Medium | Binary Tree Right Side View Python

콩이·2024년 11월 12일

leetcode python 코딩테스트

코딩테스트 Python

목록 보기

9/13

📍 문제 설명

이진 트리의 루트가 주어지면, 자신이 루트의 오른쪽에 서있다고 상상하고, 위에서 아래로 정렬된 노드의 값을 반환하세요.

📍 예시

예시 1
- Input
  
  root = [1,2,3,null,5,null,4]
- Output
  
  [1,3,4]
예시 2
- Input
  
  root = [1,null,3]
- Output
  
  [1,3]
예시 3
- Input
  
  root = []
- Output
  
  []

📍 풀이 point

🔓 Try1 🔓

# 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 []

        stack = [root]
        result = []

        while stack:
            node = stack.pop()
            result.append(node.val)
        
            if node.right:
                stack.append(node.right)
                
        return result

문제를 잘못 이해하여 무조건 맨 오른쪽에 있는 노드의 값만 가져오면 된다고 생각했다.

즉, 오른쪽에 아예 노드가 없는 경우에는 왼쪽 노드가 선택될 수도 있다는 점을 고려하지 못했다(아래와 같은 테스트 케이스를 통과 못함).

🔓 Try2 🔓

Try1에서는 무조건 오른쪽의 노드가 없을 때를 고려하지 않았기에 이번에는 오른쪽이 없을 때의 조건을 추가해주면 된다고 생각했다.

# 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 []

        stack = [root]
        result = []

        while stack:
            node = stack.pop()
            result.append(node.val)
        
            if node.right:
                stack.append(node.right)

            elif not node.right and node.left:
                stack.append(node.left)
                
        return result

하지만 이렇게 수정하여도

위와 같은 테스트 케이스를 통과할 수 없다.

해당 코드를 바탕으로 어느 방향으로 수정해야할지 감이 잘 잡히지 않아 아예 다른 방향으로 코드를 고쳤다.

🔓 Try3 🔓

# 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 []
            
        queue = deque([root])
        result = []
        
        while queue:
            level_size = len(queue)  # 현재 레벨의 노드 수를 계산
            level_value = []

            for _ in range(level_size):
                # 큐에서 현재 레벨의 노드를 하나씩 꺼냄
                node = queue.popleft()
                level_value.append(node.val)
                
                # 각 노드의 왼쪽, 오른쪽 자식을 큐에 추가
                if node.left:  
                    queue.append(node.left)
                if node.right:  
                    queue.append(node.right)

            result.append(level_value[-1])
        
        return result