파이썬으로 이진 트리의 탑 뷰(Top View) 구하는 프로그램

이진 트리가 주어졌을 때, 해당 트리의 탑 뷰(top view)를 구하는 문제입니다. 탑 뷰란 트리를 위에서 아래로 내려다볼 때 보이는 노드들을 의미하며, 결과는 반드시 왼쪽에서 오른쪽 순서로 정렬되어야 합니다.

예를 들어 다음과 같은 트리가 입력으로 주어지면 출력은 [3, 5, 8, 6, 9]가 됩니다. 노드 3이 노드 2의 바로 위에 있고, 노드 5가 노드 7의 바로 위에 있기 때문에 2와 7은 위에서 볼 수 없습니다.

접근 방법: BFS와 수평 좌표 활용

이 문제는 너비 우선 탐색(BFS)과 각 노드에 수평 좌표를 부여하는 방식으로 해결할 수 있습니다. 루트 노드의 좌표를 0으로 설정하고, 왼쪽 자식으로 내려갈 때는 좌표를 1 감소시키며, 오른쪽 자식으로 내려갈 때는 좌표를 1 증가시킵니다. 같은 좌표를 가진 노드 중에는 BFS 특성상 더 위에 있는 노드가 먼저 방문되므로, 각 좌표별로 처음 방문한 노드의 값만 저장하면 탑 뷰를 얻을 수 있습니다.

알고리즘 단계

1. view: 좌표를 키로, 노드 값을 값으로 저장하는 새로운 빈 맵(딕셔너리)을 생성합니다.
2. q: 양방향 큐(deque)를 생성합니다.
3. 큐의 끝에 쌍 (root, 0)을 삽입합니다.
4. start := inf, end := -inf로 초기화합니다.
5. 큐가 비어 있지 않은 동안 다음을 반복합니다.
   • 큐의 왼쪽에서 (node, coord)를 꺼냅니다.
   • start := min(start, coord), end := max(end, coord)로 갱신합니다.
   • coord가 view에 없다면 view[coord] := node.val을 저장합니다.
   • 노드의 왼쪽 자식이 존재하면 (왼쪽 자식, coord - 1)을 큐의 끝에 삽입합니다.
   • 노드의 오른쪽 자식이 존재하면 (오른쪽 자식, coord + 1)을 큐의 끝에 삽입합니다.
6. 결과를 담을 새 리스트 res를 생성합니다.
7. start부터 end까지 반복하면서, 해당 좌표가 view에 존재하면 그 값을 res의 끝에 추가합니다.
8. res를 반환합니다.

아래 구현 예제를 통해 더 잘 이해해 보겠습니다.

구현 예제

from collections import deque
class TreeNode:
    def __init__(self, data, left=None, right=None):
        self.val = data
        self.left = left
        self.right = right

class Solution:
    def solve(self, root):
        view = {}
        q = deque()
        q.append((root, 0))
        start = float("inf")
        end = float("-inf")
        while q:
            node, coord = q.popleft()
            start = min(start, coord)
            end = max(end, coord)
            if coord not in view:
                view[coord] = node.val
            if node.left:
                q.append((node.left, coord - 1))
            if node.right:
                q.append((node.right, coord + 1))
        res = []
        for i in range(start, end + 1):
            if i in view:
                res.append(view[i])
        return res

ob = Solution()
root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(8)
root.right.left = TreeNode(7)
root.right.right = TreeNode(6)
root.right.left.left = TreeNode(2)
root.right.right.right = TreeNode(9)
print(ob.solve(root))

입력

root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(8)
root.right.left = TreeNode(7)
root.right.right = TreeNode(6)
root.right.left.left = TreeNode(2)
root.right.right.right = TreeNode(9)

출력

[3, 5, 8, 6, 9]

복잡도 분석

모든 노드를 정확히 한 번씩 방문하므로 시간 복잡도는 O(n)이며, 좌표별로 값을 저장하는 맵과 큐에 필요한 공간 때문에 공간 복잡도 역시 O(n)입니다.