백준 / 트리 순회 / 1991번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 트리 순회 / 1991번 (실버 1단계)

문제 사이트: https://www.acmicpc.net/problem/1991

 

문제 설명

---

나의 풀이

def preorder_traversal(graph, node, result):
    if node == '.':
        return
    result.append(node)
    preorder_traversal(graph, graph[node][0], result)
    preorder_traversal(graph, graph[node][1], result)


def inorder_traversal(graph, node, result):
    if node == '.':
        return
    inorder_traversal(graph, graph[node][0], result)
    result.append(node)
    inorder_traversal(graph, graph[node][1], result)


def postorder_traversal(graph, node, result):
    if node == '.':
        return
    postorder_traversal(graph, graph[node][0], result)
    postorder_traversal(graph, graph[node][1], result)
    result.append(node)


def main():
    n = int(input())
    graph = {}

    for _ in range(n):
        node, left, right = input().split()
        graph[node] = (left, right)

    preorder = []
    inorder = []
    postorder = []

    preorder_traversal(graph, 'A', preorder)
    inorder_traversal(graph, 'A', inorder)
    postorder_traversal(graph, 'A', postorder)

    print(''.join(preorder))
    print(''.join(inorder))
    print(''.join(postorder))


if __name__ == "__main__":
    main()

---

※ 알아야 할 것

 

• 전위 순회 (Preorder Traversal)
  • 순서: Root → Left → Right
  • 예시: ABDCEFG
• 중위 순회 (Inorder Traversal)
  • 순서: Left → Root → Right
  • 예시: DBAECFG
• 후위 순회 (Postorder Traversal)
  • 순서: Left → Right → Root
  • 예시: DBEGFCA