S1 1991. 트리 순회

문제 보기 :  1991번: 트리 순회

---

문제

• 정답률 : 67%

---

작성 코드

# 전위 순회: 현재 노드 → 왼쪽 자식 → 오른쪽 자식
def preorder(node):
    if node == '.':  # 자식이 없는 경우
        return ''
    return node + preorder(tree[node][0]) + preorder(tree[node][1])

# 중위 순회: 왼쪽 자식 → 현재 노드 → 오른쪽 자식
def inorder(node):
    if node == '.':  # 자식이 없는 경우
        return ''
    return inorder(tree[node][0]) + node + inorder(tree[node][1])

# 후위 순회: 왼쪽 자식 → 오른쪽 자식 → 현재 노드
def postorder(node):
    if node == '.':  # 자식이 없는 경우
        return ''
    return postorder(tree[node][0]) + postorder(tree[node][1]) + node

# 트리 정보 입력 처리
N = int(input())  # 노드의 개수
tree = {}  # 트리를 딕셔너리로 표현

# 각 노드와 자식 노드 정보 입력
for _ in range(N):
    parent, left, right = input().split()
    tree[parent] = (left, right)

# 결과 출력: 전위 순회, 중위 순회, 후위 순회
print(preorder('A'))  # 루트 노드 'A'에서 시작
print(inorder('A'))
print(postorder('A'))

---

풀이

먼저 트리의 정보를 입력받아 각 노드의 왼쪽 자식과 오른쪽 자식을 딕셔너리 형태로 저장한다.

자식 노드가 없는 경우 '.'으로 처리한다.

전위 순회는 현재 노드를 먼저 방문한 뒤 왼쪽 자식, 오른쪽 자식 순서로 탐색하며 결과를 누적한다.
중위 순회는 왼쪽 자식을 먼저 탐색한 뒤 현재 노드, 오른쪽 자식 순서로 탐색하며 결과를 누적한다.
후위 순회는 왼쪽 자식과 오른쪽 자식을 모두 탐색한 뒤 현재 노드를 방문하며 결과를 누적한다.

각 순회는 재귀적으로 구현하며, 자식 노드가 없을 때는 종료한다. 마지막으로 루트 노드 A를 시작으로 전위, 중위, 후위 순회 결과를 각각 출력한다.