🌞 Tree: Top View

🚊 문제 설명

• binary tree의 root node에 대한 포인터가 주어지면 binary tree의 top view를 print할 것.
• top view란, node의 위에서 본 tree를 뜻함.

  예시 1.
input : 1 2 5 3 4 6

     1
      \
       2
        \
         5
        /  \
       3    6
        \
         4

  Top View : 1 → 2 → 5 → 6
  
  

  예시 2.
input : 1 10 4 3 2 7 5 6 11 15 13 17

          1
            \
             10
            /  \
          4      11
         / \      \
       3    7       15
      /    /  \    /  \  
     2    5    6  13   17

  Top View : 2 → 3 → 1 → 10 → 11 → 15 → 17

입력 예시

             1 2 5 3 4 6

   1
    \
     2
      \
       5
      /  \
     3    6
      \
       4

출력 예시

1 2 5 6

설명

From the top, only nodes 1, 2, 5, 6 are visible.

🚢 기본 제공 Code

class Node:
    def __init__(self, info): 
        self.info = info  
        self.left = None  
        self.right = None 
        self.level = None 

    def __str__(self):
        return str(self.info) 

class BinarySearchTree:
    def __init__(self): 
        self.root = None

    def create(self, val):  
        if self.root == None:
            self.root = Node(val)
        else:
            current = self.root
         
            while True:
                if val < current.info:
                    if current.left:
                        current = current.left
                    else:
                        current.left = Node(val)
                        break
                elif val > current.info:
                    if current.right:
                        current = current.right
                    else:
                        current.right = Node(val)
                        break
                else:
                    break

🚢 Input & Output

tree = BinarySearchTree()
t = int(input())

arr = list(map(int, input().split()))

for i in range(t):
    tree.create(arr[i])

topView(tree.root)

📑 Code 1 : BFS

📌 Logic 설명

• 위에서 바라봤을 때 최초로 보이는 Node만 담아야 하는 조건을 고려하여 tree에서의 상하 level 개념을 빗대어 좌우 level 개념을 depth라는 값으로 활용
• 전체 Node를 탐색하면서 조건에 맞는 Node만 찾아야 하므로 BFS 개념 사용

from collections import deque

def topView(root):
	# 결과를 담을 dict 생성
    #   depth(해당 노드의 좌우 폭의 단계)와 node.info(해당 노드의 value)를 dict 형태로 담을 예정
    result = {}
    # queue 자료구조 이용을 위해 deque 함수 사용
    queue = deque([])
    # root node부터 진행하기 위해 queue에 추가
    #   좌우 폭의 단계(depth)를 숫자로 표현하기 위해 각 노드를 [node, depth] 로 표현
    #   root node는 [root, 0]으로 표현
    queue.append(([root,0]))
    # queue가 빌 때까지 진행
    while(queue):
    	# 현재 level에서 가장 앞에 있는(depth가 가장 낮은) node를 선택
        current_node = queue.popleft()
        # 만약, 해당 depth의 node에 대한 데이터가 result에 없다면
        if not current_node[1] in result:
        	# 현재 노드의 depth:info 를 result에 추가
            result[current_node[1]] = current_node[0].info
        # 만약, 현재 노드의 왼쪽 자식 노드가 있다면
        if current_node[0].left:
        	# 그 노드를 [node, depth] 형태의 자료형으로 queue에 추가
            #   그 노드의 depth는 현재 노드의 depth보다 1이 작음 (왼쪽으로 이동하니까)
            queue.append([current_node[0].left, current_node[1]-1])
        # 만약, 현재 노드의 오른쪽 자식 노드가 있다면
        if current_node[0].right:
            # 그 노드를 [node, depth] 형태의 자료형으로 queue에 추가
            #   그 노드의 depth는 현재 노드의 depth보다 1이 큼 (오른쪽으로 이동하니까)
            queue.append([current_node[0].right, current_node[1]+1])
    # depth 기준으로 dict를 정렬하기 위해 items() 메서드를 사용
    #   depth 기준으로 정렬 시, top view 기준으로 왼쪽부터 순서대로 정렬됨.
    for depth, value in sorted(result.items()):
        print(str(value), end=" ")

📑 Code 2 : DFS

📌 Logic 설명

• 위에서 바라봤을 때 최초로 보이는 Node만 담아야 하는 조건을 고려하여 tree에서의 상하 level 개념을 빗대어 좌우 level 개념을 depth라는 값으로 활용
• root Node부터 시작하여 연결된 자식 Node들에 대해 level을 낮춰가며 depth와 count(root node로부터의 이동 횟수)를 계산 → DFS 개념을 사용하는 이유
• depth가 동일한 Node들에 대해서는 count가 적은 Node가 top view에서 발견되는 Node라는 점을 코드로 구현

# binary tree의 모든 Node에 대해 depth(좌/우 level)와 count(이동 횟수)를 계산하여 위에서 언급한 조건에 맞는 Node만 추출하는 함수를 생성
def traversal(root, depth, count, temp):
	# root Node가 없으면 종료시킴
    if root is None:
        return
    # 현재 노드의 depth가 temp에 없다면
    if depth not in temp:
    	# 현재 노드의 depth와 [value, count]를 dictionary 형태로 temp에 담음
        temp[depth] = [root.info, count]
    # 현재 노드와 동일한 depth를 갖는 노드가 temp에 있는 경우,
    #   해당 노드의 count보다 현재 노드의 count가 더 작다면
    if count < temp[depth][1]:
    	# 그 depth를 갖는 노드의 정보를 현재 노드의 정보로 갱신
        #  한마디로 지금 노드의 depth, info, count로 바꿔준다 이말임
        #    왜냐면, count가 작다는 것은 이동을 적게했다는 것이고 그 말인즉 
        #    상위 level에 위치한 Node이기 때문에 top view에서 먼저 보인다는 것이기 때문
        temp[depth] = [root.info, count]
    # 재귀를 호출하여 우측/좌측 모두 전부 계산
    #   이동해서 찾는 것인데, 이동은 무조건 count가 (+1)되고, 
    #   좌/우 여부에 따라 depth는 (-1) 혹은 (+1)됨.
    traversal(root.right, depth + 1, count + 1, temp)
    traversal(root.left, depth - 1, count + 1, temp)

def topView(root):
	# top view로 바라보았을 때의 결과를 담을 dict 선언
    temp = dict()
    # root Node부터 전부 탐색하여 결과를 dict에 담음
    traversal(root, 0, 0, temp)
    # depth 기준으로 dict를 정렬하기 위해 items() 메서드를 사용
    #   depth 기준으로 정렬 시, top view 기준으로 왼쪽부터 순서대로 정렬됨.
    for i in sorted(temp.items()):
        print(i[1][0], end = ' ')