[BAEKJOON 백준] 1991 트리 순회 (PYTHON)

 

https://www.acmicpc.net/problem/1991

1991번: 트리 순회

문제

이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.

예를 들어 위와 같은 이진 트리가 입력되면,

• 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)
• 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)
• 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)

가 된다.

입력

첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자 대문자로 매겨지며, 항상 A가 루트 노드가 된다. 자식 노드가 없는 경우에는 .으로 표현된다.

출력

첫째 줄에 전위 순회, 둘째 줄에 중위 순회, 셋째 줄에 후위 순회한 결과를 출력한다. 각 줄에 N개의 알파벳을 공백 없이 출력하면 된다.

 

이 문제는 DFS를 활용을 해서 문제를 해결했습니다.

preoder, inorder, postorder 세 개로 나눠서 출력을 하도록 했습니다.

아래에 만들어 진것처럼 preoder의 경우 호출하기전에 print를 하게 되있고,

inorder을 중간에 print를 하고, postorder은 마지막에 print를 하게 해서 세가지를 제작할 수 있었습니다.

class Node:
    def __init__(self, item, left, right):
        self.item = item
        self.left = left
        self.right = right


def preorder(node):  # 전위 순회
    print(node.item, end='')
    if node.left != '.':
        preorder(tree[node.left])
    if node.right != '.':
        preorder(tree[node.right])


def inorder(node):  # 중위 순회
    if node.left != '.':
        inorder(tree[node.left])
    print(node.item, end='')
    if node.right != '.':
        inorder(tree[node.right])


def postorder(node):  # 후위 순회
    if node.left != '.':
        postorder(tree[node.left])
    if node.right != '.':
        postorder(tree[node.right])
    print(node.item, end='')


if __name__ == "__main__":

    N = int(input())
    tree = {}

    for _ in range(N):
        node, left, right = map(str, input().split())
        tree[node] = Node(item=node, left=left, right=right)

    preorder(tree['A'])
    print()
    inorder(tree['A'])
    print()
    postorder(tree['A'])

 

아래의 방식은 DFS를 한번만 실행을 하면, 각각의 답에 하나씩 값들을 넣어주는 방식으로 문제를 해결했습니다.

class Node:
    def __init__(self, item, left, right):
        self.item = item
        self.left = left
        self.right = right


def DFS(node):
    global preAnswer
    preAnswer += node.item
    if node.left != '.':
        DFS(tree[node.left])
    global inAnswer
    inAnswer += node.item
    if node.right != '.':
        DFS(tree[node.right])
    global postAnswer
    postAnswer += node.item


if __name__ == "__main__":

    N = int(input())
    tree = {}
    preAnswer = ""
    inAnswer = ""
    postAnswer = ""
    for _ in range(N):
        node, left, right = map(str, input().split())
        tree[node] = Node(item=node, left=left, right=right)

    DFS(tree['A'])
    print(preAnswer)
    print(inAnswer)
    print(postAnswer)