[LeetCode] 199. Binary Tree Right Side View (medium, python)

https://leetcode.com/problems/binary-tree-right-side-view/description/?envType=study-plan-v2&envId=top-interview-150

Binary Tree Right Side View - LeetCode

아이디어

처음 문제를 보고 TreeNode를 리스트로 변환해야겠다고 생각했다. 그래서 떠올린 해결법은 다음과 같다.

1. tree 리스트 만들기 [(value, level), ...]

2. 각 level에서 제일 뒤의 값을 가져오기

 

tree 리스트

tree 리스트를 만들기 위해서 bfs를 사용하였다.

bfs를 사용한 탐색 순서는 아래와 같다.

       1

     2 3

  4 5 6 7

8 9 10 11 12 13 ...

 

이를 코드로 구현하여 tree 리스트를 만들었다. 

queue = deque()
queue.append((root, 0))

tree = []
while queue:
    curr, level = queue.popleft()

    if curr == -1:
        continue

    tree.append((curr.val, level))

    if curr.left or curr.right:
        if curr.left: queue.append((curr.left, level + 1))
        else: queue.append((-1, level + 1))

        if curr.right: queue.append((curr.right, level + 1))
        else: queue.append((-1, level + 1))

    else:
        continue

 

 

전체 코드

# 8:08 ~ 9:41 (1'33")

# 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

from collections import deque

class Solution:

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

        if not root:
            return []


        queue = deque()
        queue.append((root, 0))

        tree = []
        while queue:
            curr, level = queue.popleft()

            if curr == -1:
                continue

            tree.append((curr.val, level))
            
            if curr.left or curr.right:
                if curr.left: queue.append((curr.left, level + 1))
                else: queue.append((-1, level + 1))

                if curr.right: queue.append((curr.right, level + 1))
                else: queue.append((-1, level + 1))
            
            else:
                continue
        
        tree.reverse()

        answer = []
        level = -1
        for t, l in tree:
            if level == l: continue

            level = l
            answer.append(t)

        answer.reverse()
        return answer

 

다른 사람의 코드

문제를 풀면서 dfs를 사용하면 메모리 낭비나 연산 횟수를 줄일 수 있을 것 같다는 생각이 들었다. 그래서 다른 사람들의 풀이를 찾아보았다.

def rightSideView(self, root: TreeNode) -> List[int]:
        def dfs(root, result_list, level):
            if not root:
                return
            if root and level == len(result_list):
                result_list.append(root.val)
            dfs(root.right, result_list, level+1)
            dfs(root.left, result_list, level+1)
            return result_list
        return dfs(root, [], 0)

dfs로 오른쪽 값 부터 방문하며, 해당 레벨에 처음 방문할 시에만 값을 저장한다. level을 따로 저장하지도 않고, 바로 정답 리스트를 반환하기 때문에 훨씬 좋은 코드라고 생각한다. 

아래 글을 참고하여 dfs로도 풀어보면 좋을 것 같다. (코드 출처)

 

https://zhenyu0519.github.io/2020/03/12/lc199/

leetcode 199. Binary Tree Right Side View (Python)