백준 1991번: 트리 순회 (Python)

1991번: 트리 순회

트리의 순회 방식 3가지를 알면 쉽게 풀 수 있는 문제다. 

Preorder (전위 순회)

루트부터 먼저 방문한 다음 왼쪽 하위 트리, 오른쪽 하위 트리 순으로 방문하는 방식

Inorder (중위 순회)

왼쪽 하위 트리 먼저 방문하고 이후 루트 트리, 오른쪽 하위 트리 순으로 방문하는 방식

Postorder (후위 순회)

왼쪽 하위 트리 먼저 방문한 후 이후 오른쪽 하위 트리, 마지막으로 루트 트리를 방문하는 방식

 

딕셔너리로 노트 이름을 저장해 set으로 양쪽 자식들을 저장했다.

n = int(input())
nodes = {}
for i in range(n):
    node, leftnode, rightnode = input().split()
    nodes[node] = (leftnode, rightnode)

def preorder(node):
    print(node, end="")
    if nodes[node][0] != ".":
        preorder(nodes[node][0])
    if nodes[node][1] != ".":
        preorder(nodes[node][1])

def inorder(node):
    if nodes[node][0] != ".":
        inorder(nodes[node][0])
    print(node, end="")
    if nodes[node][1] != ".":
        inorder(nodes[node][1])

def postorder(node):
    if nodes[node][0] != ".":
        postorder(nodes[node][0])
    if nodes[node][1] != ".":
        postorder(nodes[node][1])
    print(node, end="")

preorder("A")
print()
inorder("A")
print()
postorder("A")

위 3가지 방식이 있는데 코드로는 재귀로 더 간단하게 나타낼 수 있다. 전위 중위 후위 헷갈릴 수 있는데 루트가 언제 방문하는지를 생각하면서 나누면 방지할 수 있다. 

전위 = 루트를 처음 방문, 중위 = 루트를 중간에 방문, 후위 = 루트를 나중에 방문