[알고리즘/python] LeetCode 199. Binary Tree Right Side View - BFS 풀이

📑 1. 문제 이해

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

Binary Tree Right Side View - LeetCode

이 문제는 이진 트리의 각 레벨에서 가장 오른쪽에 위치한 노드의 값을 리스트로 반환하는 문제입니다.  이때 주의할 점은 다음과 같습니다.

- 트리는 빈 트리일 수 있습니다. 매개변수 root가 None일 수 있습니다.

- 노드의 값은 음수일 수 있습니다.

- 가장 상위 레벨의 결과값부터 배열에 저장되어야합니다.

☑️ 테스트케이스

문제에서 주어진 테스트케이스는 다음과 같습니다.

 

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

- 가장 오른쪽 노드는 부모 노드를 기준으로 오른쪽에 위치합니다. 즉, 루트 노드를 기준으로 오른쪽 노드만 따라가면 가장 오른쪽 노드들을 찾을 수 있습니다.

 

Example2: root = [1,null, 3]

- Example1과 마찬가지입니다.

 

다음과 같은 경우를 추가로 살펴볼 필요가 있습니다.

 

root = []

- 빈 트리입니다

 

root = [1, 2]

- 마지막 레벨에 노드가 가득차지 않고, 왼편에 위치합니다. 가장 오른쪽은 비어있습니다. 

 

Input으로 주어진 배열이 실제로 함수의 매개변수로 어떻게 들어오는지 알고 싶다면  이전 발행 글 의 배열로 트리 만들기를 참고해주세요.

💡 2. 알고리즘 설계

트리의 노드들을 레벨별로 살펴보기 위해서 넓이 우선 탐색(BFS)알고리즘을 사용할 수 있습니다. 이때, 큐에 노드와 그 노드이 레벨을 함께 기록한다면 노드를 레벨별로 구분할 수 있습니다. 또한, 큐에 왼쪽 자식 노드, 오른쪽 자식 노드 순으로 넣는다면 같은 레벨에서 가장 마지막에 살펴본 노드가 가장 오른쪽 노드라고 판단할 수 있습니다. 

1. 빈 큐에 (루트 노드, 0)의 튜플을 넣습니다. 루트 노드의 레벨은 0입니다.

2. 큐에서 튜플을 하나 꺼냅니다. 현재 레벨과 결과 배열의 길이(결과 배열의 길이 = 마지막 살펴본 노드의 레벨)를 비교합니다.

    - 현재 레벨이 마지막 살펴본 노드의 레벨과 같다면, 이전 결과 배열의 값을 갱신합니다. 현재 노드가 이전 노드보다 더 오른쪽 노드입니다.

    - 현재 레벨이 마지막 살펴본 노드의 레벨과 다르다면(더 큼), 이전 레벨의 노드를 모두 살핀 것이므로 결과 배열에 새롭게 값을 추가합니다.

3. 현재 노드의 자식이 있다면 왼쪽 자식 오른쪽 자식 노드 순으로 넣습니다. 동일 레벨의 가장 오른쪽 자식이 가장 마지막에 큐에 삽입됩니다.

4. 큐가 빌때까지 즉, 모든 노드를 방문할때까지 위의 2, 3을 반복합니다.

    def rightSideView(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        result = []
        queue = deque()
        queue.append((root, 0))
        while queue:
            node, level = queue.popleft()
            if level < len(result):
                result[level] = node.val
            else:
                result.append(node.val)
            if node.left:
                queue.append((node.left, level + 1))
            if node.right:
                queue.append((node.right, level + 1))
        return result

시간 복잡도 및 공간 복잡도

시간 복잡도: O(N). 모든 노드들이한번만 queue에 들어갔다 빠지기때문에 O(N)복잡도가 됩니다

공간 복잡도: O(N). 큐에 최대 저장되는 노드의 개수는 동일 레벨 노드 개수의 최대값입니다. 동일 레벨 노드 개수의 최대값은 최하위 계층이 가득찬 경우로 2 ^ h(h는 트리의 높이)이고 h는 LogN이므로 O(2^(LogN)) = O(N)이 됩니다.

 

⚒️ 3. 최적화

큐를 레벨별로 교체하며 사용한다면 큐에 레벨을 함께 기록하지 않고도 레벨별로 탐색이 가능합니다. 큐에 동일 레벨의 노드만 기록하고, 자식 레벨의 노드들을 새로운 큐에 기록합니다. 현재 레벨의 노드를 모두 방문하였다면 큐를 다음 레벨의 노드들을 담은 큐로 교체합니다.

 또한 큐에 오른쪽자식에서 왼쪽자식 순으로 기록한다면 큐에서 처음으로 제거된 노드만 결과 배열에 저장하면 되고 나머지 노드들에 대해서 결과 배열과 비교하거나 갱신하지 않아도 되어 불필요한 연산을 줄일 수 있습니다. 큐에 가장 먼저 삽입된 노드가 가장 오른쪽 노드입니다. 

    def rightSideView(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        result = []
        queue = deque()
        queue.append(root)
        while queue:
            next_queue = deque()
            size = len(queue)
            for n in range(size):
                node = queue.popleft()
                if n == 0:
                    result.append(node.val)
                if node.right:
                    next_queue.append(node.right)
                if node.left:
                    next_queue.append(node.left)
            queue = next_queue
        return result

시간 복잡도 및 공간 복잡도

시간 복잡도: O(N). 위의 풀이와 마찬가지로 모든 노드가 한번씩 큐에 저장되고 삭제되므로 O(N) 복잡도를 가집니다. 하지만 불필요한 연산을 줄임으로서 실제 실행 시간은 53ms -> 38ms로 줄어들었습니다. 

 

공간 복잡도: O(N). 위의 풀이와 같습니다. 

 ⎌ 4. 검토

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

- 루트 노드로부터 오른쪽 자식을 따라 위치하는 1, 2, 4가 큐의 맨 처음에 저장됩니다. 그 값이 결과 배열에 저장됩니다. 마지막 레벨을 방문하고 나면 queue가 []이 되어 반복문이 종료됩니다.

 

Example2: root = [1,null, 3]

- 루트 노드로부터 오른쪽 자식을 따라 위치하는 1, 3이 큐의 맨 처음에 저장됩니다. 두번째 반복문시 queue = [3]으로 for문이 한번만 실행되고 종료됩니다. 이후 queue = []가 되어 반복문이 종료됩니다.

 

root = []

- 빈 트리인 경우 함수의 맨 처음에 체크해 빈 배열을 반환합니다. 만약 빈 배열을 체크하지 않는다면 큐에 None이 추가되어 큐는 더이상 빈 큐가 아니게 됩니다. 따라서 반복문이 실행되어 Attribute Error가 발생합니다. 

 

root = [1, 2]

- 마지막 레벨에 노드가 가득차지 않지만 2가 큐의 가장 처음에 삽입되므로 결과 배열에 추가됩니다. 존재하는 자식들에 대해서만 큐에 삽입되므로 없는 경우에는 큐에 삽입되지 않습니다.

---

✅ 정리

◎ 넓이 우선 탐색시에 레벨 별로 나눠서 살펴보기 위해서는 1) queue를 레벨 별로 교체하면서 사용하거나 2) 큐에 삽입할때 level을 함께 넣어줄 수 있습니다.