[백준] 1991_트리 순회 (python)

👉 1991_트리 순회

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

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

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

👉 입력

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

👉 출력

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

👉 예제

✍ 내 코드

---

# 실버 1레벨        트리 순회
from collections import defaultdict
from sys import stdin

read = stdin.readline
N = int(read())
tree = defaultdict(list)
for _ in range(N):
    root, l, r = read().strip().split()
    tree[root] = [l, r]
result = ["", "", ""]

def traverse(node):
    result[0] += node
    if tree[node][0] != ".":
        traverse(tree[node][0])

    result[1] += node
    if tree[node][1] != ".":
        traverse(tree[node][1])

    result[2] += node

traverse("A")

for i in result:
    print(i)

---

✍ 팁

• traverse 함수를 보면 알겠지만 어느 부분에서 값을 저장(or print)하냐에 따라서 전위, 중위, 후위 순회가 된다.
• dict를 이용하여 그래프를 만들면 간단히 구현 할 수 있다.
  (해당 문제는 defaultdict가 큰 이점이 없지만 여러 문제에서 큰 이점을 갖게 되니 모르시는 분들은 알아보길 권장한다. 코드가 훨씬 파이써닉해질거라 생각한다.)

✍ 잡담

최근 SW마에스트로 준비로 TIL외에 글을 잘 안 올리다가 포스팅을 했다.
알고리즘 문제를 해결하고나면 항상 검색해서 다른이의 풀이를 보고 참고하는데
이번 문제를 검색해보니 모두 순회를 불필요하게 3번씩 하는 것을 보고 포스팅을 했다.