Problem :

https://www.hackerrank.com/challenges/tree-top-view/problem


My Solution :

from collections import deque


def topView(root):
pos = 0
pos_dic = {}
queue = deque()
queue.append((root, pos))
while queue:
node, pos = queue.popleft()
if pos not in pos_dic:
pos_dic[pos] = node.info
if node.left:
queue.append((node.left, pos-1))
if node.right:
queue.append((node.right, pos+1))
for pos, info in sorted(pos_dic.items()):
print(info, end=' ')


Comment :

정말 하루종일 나를 괴롭혔던 문제인데 풀고 나니 뿌듯하다. 나를 괴롭혔던 이유는 이 문제가 해석에 따라 오해의 소지를 품고 있기 때문이다. 실제로 Discussions에 엄청 말이 많다.


예를 들어 위와 같은 트리를 가정해보자. Top에서 보면 7이 과연 보일까? 상식적으로 5보다 7이 크기 때문에 5보다 7이 오른쪽에 있어야 하고, 따라서 7은 5에 가려서 보이지 않아야 정상이다. 적어도 우리가 알고 있는 BST는 그렇다. 하지만 이 문제에서는 다르다. 이 문제에서는 7이 보인다고 설정하고 풀어야 한다. 즉 root 노드에서 좌우로 떨어진 거리를 1씩 카운트해서 그 거리가 더 멀다면 7이 5에 가리지 않고 보인다는 것이다. 그러니까 위 그림에서는 5와 8이 왼쪽으로 같은 거리이고 7은 왼쪽으로 한칸 더 나와있다고 해석해야 한다. 그렇게 해석하고 정사영이라 생각하고 풀면 된다.


나는 queue를 사용하여 탐색을 BFS(level-order)로 하고 출력은 root에서 좌우로 떨어진 거리 기준 왼쪽부터 출력하였다. 탐색을 BFS로 한 이유는 root에서 좌우로 같은 거리만큼 떨어진 노드 중 먼저 탐색되었던(높은 곳에 있던) 노드가 위에서 봤을 때 눈에 보이기 때문이다.