[Leetcode]Binary Tree Right Side View

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

LeetCode - The World's Leading Online Programming Learning Platform

 

문제 분석

이진 트리가 주어졌을때 오른쪽에서 본 순서대로 출력합니다.

 

처음 시도한 답안 - 실패

# 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]:
        def dfs(root, answer):
            if root is None:
                return
            
            answer.append(root.val)
            dfs(root.right, answer)

            return answer

        return dfs(root, [])

접근 방법

1. 처음에 시도했던 방법입니다. 트리를 DFS 알고리즘으로 순회합니다.
2. 트리의 오른쪽 노드만 순회하면서 answer 배열에 추가합니다.

하지만 이렇게 되는 경우에 input = [1,2] 인 케이스를 커버할 수 없습니다. ouput = [1], expected_output = [1,2]로 실패하게 됩니다. 오른쪽에서 보는 상황이므로 오른쪽 노드가 없다면 왼쪽 노드인 2가 보이도록 정답이 나와야 합니다.

 

두번째로 시도한 답안

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

        answer = {}

        def dfs(root, level, answer):
            if not root:
                return
            
            answer[level] = root.val

            dfs(root.left, level+1, answer)
            dfs(root.right, level+1, answer)

        dfs(root, 0, answer)

        return answer.values()

접근 방법

1. DFS 알고리즘을 활용하는 것은 똑같습니다.
2. DFS 내부에서
   1. answer 딕셔너리에 level과 함께 들어온 노드의 값을 기록합니다.
   2. 이후 왼쪽과 오른쪽 노드를 level을 1 증가시켜 재귀 호출 합니다.
3. 오른쪽 노드를 나중에 탐색하므로 해당 레벨에서 가장 오른쪽에 위치한 노드가 answer에 기록됩니다.

트리를 탐색하는 알고리즘은 DFS를 이용하였고, 레벨을 이용하고 오른쪽을 후순위로 탐색함으로써 오른쪽에서 보이는 값을 찾을 수 있었습니다.