[LeetCode | Python] 199. Binary Tree Right Side View

느낀점

가볍게 접근하고 가볍게 풀었지만, 놓친 부분이 있었던 것 같아 조금은 아쉬웠던 문제

문제

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

 

이진 트리에서 레벨별로 오른쪽에 있는 값을 리스트로 반환하라.

풀이

해당 문제는 BFS, DFS든 모든 노드를 탐색해야만 한다고 생각해서 재귀에 기반한 DFS 형태로 문제를 풀었다. 속도 측면에서는 손해보는 지점이 없었고 문제도 잘 풀렸지만, 앞으로는 다음을 고려해야 한다.

• 재귀로 인해 오버헤드가 발생할 수 있어 메모리 효율성 측면에서 큐 방식의 반복문이 더 나을 수 있다.
• 레벨별로 처리한다는 의미에서 BFS가 조금 더 직관적이다.
• 깊은 트리의 경우 재귀 길이 제한으로 인해 스택 오버 플로우가 발생할 가능성이 있다.

# 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]:
        result = []

        def right_first_navigation(node, depth):
            if len(result) == depth:
                result.append(node.val)

            if node.right:
                right_first_navigation(node.right, depth+1)

            if node.left:
                right_first_navigation(node.left, depth+1)
        
        if root:
            right_first_navigation(root, 0)

        return result

 

결과

• 공간복잡도: $$ O(N) $$
• 시간복잡도: $$ O(N) $$