[Leetcode] 199. Binary Tree Right Side View

#1.  문제

https://leetcode.com/problems/binary-tree-right-side-view/

Binary Tree Right Side View - LeetCode

 

 

이진 탐색 트리가 주어질 때, 트리의 오른쪽에서 바라볼 수 있는 값들을 찾는 문제.

즉, 각 depth에서 가장 오른쪽에 있는 값을 찾으면 된다.

Input: 
root = [1,2,3,null,5,null,4]

Output: 
[1, 3, 4]

Explanation:
옆에서 보면 보이는 값들은 
level_1 : 1
level_2 : 3
level_3 : 4

---

#2.  풀이

 

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]:
        import collections
        q = collections.deque()

        output = collections.defaultdict(list)

        height = 0
        
        if root:
            q.append(root)
        while q:
            for _ in range(len(q)):
                cur = q.popleft()
                if cur.left:
                    q.append(cur.left)
                if cur.right:
                    q.append(cur.right)
                output[height].append(cur.val)
            height += 1

        result = [value[-1] for value in output.values()]
        
        return result

 

 

각 뎁스마다 어떤 값이 들어오는지 기록하고, 뎁스의 마지막 값이 결국 오른쪽에서 보는 값이라고 할 수 있다.

각 뎁스의 모든 값을 우선적으로 탐색해야하므로 Queue를 활용한 너비탐색을 진행한다.

문제의 답을 도출하는 경로는 쉬웠지만, 코드로 구현하는 데 조금 애를 먹은 문제