[Python] 백준 2263 트리의 순회

 

 

문제

n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다. 이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오.

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

 

 

 

 

 

 

 

 

난이도

골드 1

 

 

 

 

 

코드

import sys
sys.setrecursionlimit(10**6)

def find_tree(start_index, end_index, parent_node, left_or_right) :
    global root_index
    
    # print("start : " , start_index, "end : ", end_index, "parent_node : ",parent_node, "? : ", left_or_right)
    
    root_node = post_order[root_index]

    parent[root_node] = parent_node
    if left_or_right == 'L' :
        left_child[parent_node] = root_node
    else :
        right_child[parent_node] = root_node

    in_root_index = node_index[root_node]

    # 오른쪽으로 보내기
    if end_index > in_root_index :
        root_index -= 1
        find_tree(in_root_index+1, end_index, root_node, 'R')

     # 왼쪽으로 보내기
    if start_index < in_root_index :
        root_index -= 1
        find_tree(start_index, in_root_index-1,root_node, 'L')


def pre_order(root) :
    print(root,end=' ')
    if left_child[root] != -1 :
        pre_order(left_child[root])
    if right_child[root] != -1 :
        pre_order(right_child[root])

n = int(sys.stdin.readline())
in_order = list(map(int,sys.stdin.readline().split()))
post_order = list(map(int,sys.stdin.readline().split()))
left_child = [-1] * (n+1) # 왼쪽 자식
right_child = [-1] * (n+1) # 오른쪽 자식
parent = [-1] * (n+1) # 부모
node_index = [-1] * (n+1)
for i in range(n) :
    value = in_order[i]
    node_index[value] = i

root_index = n-1
find_tree(0,n-1,0,'L')

# 전위순회 출력
pre_order(post_order[-1])

 

 

 

 

풀이

처음엔 막막하다 느꼈는데 손으로 직접 풀어보니까 알고리즘이 떠올랐다.

우선 중위순회, 후위순회, 전위순회가 무엇인지 알아야한다.

 

 

 

• 중위순회 (in-order): 왼쪽 서브트리 → 루트 → 오른쪽 서브트리
• 후위순회 (post-order): 왼쪽 서브트리 → 오른쪽 서브트리 → 루트
• 전위순회 (pre-order): 루트 → 왼쪽 서브트리 → 오른쪽 서브트리

 

전체 흐름

1. 입력된 중위순회와 후위순회 데이터를 기반으로 트리를 복원
2. 후위순회의 마지막 노드부터 시작하여 트리의 각 노드를 재귀적으로 탐색하면서 자식 노드와 부모 노드를 설정
3. 복원된 트리에서 전위순회 방식으로 노드를 출력

 

우선 중위순회(in-order)와 후위순회(post-order) 데이터를 이용해 트리를 복원해야 한다. 여기서 중요한 점은 후위순회에서 뒤에 있는 노드일수록 루트에 가깝다는 것

• 가장 마지막에 있는 노드가 트리의 루트 노드
• 이 루트 노드를 기준으로,중위순회 데이터를 사용해 왼쪽 서브트리와 오른쪽 서브트리로 나눌 수 있다.
• 이후 나눠진 서브트리들을 재귀적으로 처리

 

재귀 함수에서는 

1. 부모 노드를 설정
2. 해당 노드를 부모로 하는 왼쪽 자식과 오른쪽 자식을 연결

여기서 중요한 점은 오른쪽 서브트리를 먼저 처리해야 한다는 것

그래야 후위순회에서 루트를 찾기 위해 인덱스를 차례로 감소시킬 수 있다.

트리 복구가 완료되면 전위순회(pre-order) 함수를 사용해 트리를 출력. 이 부분은 비교적 간단하다.