📚 1991 - 트리 순회

트리 순회

풀이

문제는 전형적인 트리 순회 알고리즘 문제이다.
전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)

만약, 전위, 중위, 후위에 대해 모른다면
전위, 중위, 후위 설명
이를 참고하면 될 것 같다.

Pre-order(전위순회)
1) 루트노드 방문
2) 왼쪽 자식 노드를 루트로 하는 서브 트리를 프리오더(재귀)
3) 오른쪽 자식 노드를 루트로 하는 서브 트리를 프리오더(재귀)

In-order(중위순회)
1) 왼쪽 자식 노드를 루트로 하는 서브 트리를 인오더(재귀)
2) 루트노드 방문
3) 오른쪽 자식 노드를 루트로 하는 서브 트리를 인오더(재귀)

Post-order(후위순회)
1) 왼쪽 자식 노드를 루트로 하는 서브 트리를 포스트오더(재귀)
2) 오른쪽 자식 노드를 루트로 하는 서브 트리를 포스트오더(재귀)
3) 루트노드 방문

소스

# 트리 순회

import sys

n = int(sys.stdin.readline())

# 문자열 배열일 때는 딕셔너리 사용하기

tree = {}


def pre_order(root):
    if root != ".":
        print(root, end="")
        pre_order(tree[root][0])
        pre_order(tree[root][1])

def mid_order(root):
    if root != ".":
        mid_order(tree[root][0])
        print(root, end="")
        mid_order(tree[root][1])

def post_order(root):
    if root != ".":
        post_order(tree[root][0])
        post_order(tree[root][1])
        print(root, end="")

for _ in range(n):
    node, left, right = sys.stdin.readline().split()

    tree[node] = [left, right]

pre_order('A')
print()
mid_order('A')
print()
post_order('A')
print()

채점 결과